Задача №112804. Выборы президента
Мистер Скрудж — председатель местного парламента. На повестке дня в парламенте выбор президента. Конечно, президентом нужно выбрать одного из парламентариев. В парламенте есть две фракции — Даки и Маусы. Членам обеих партий запрещено голосовать за политиков, которые состоят в той же партии, что и голосующий. Председатель парламента, то есть, Скрудж, не имеет права голоса, и не может быть избран президентом.
В процессе выборов каждый из парламентариев проголосовал ровно за одного парламентария, состоящего в другой партии. После этого список, в котором указано, сколько голосов получил каждый из политиков, был передан Скруджу.
Получив список, Скрудж понял, что он не знает, в какой партии состоит какой кандидат, а это важно. Помогите ему составить какое-либо распределение политиков по партиям, удовлетворяющее всем условиям, или выясните, что список, который получил Скрудж, некорректен.
В первой строке входного файла дано целое число \(n\) (\(2 \le n \le 100\,000\)) — число парламентариев.
В следующей строке дано \(n\) целых чисел \(a_i\) (\(0 \le a_i < n\), сумма всех \(a_i\) равна \(n\)) — число голосов, которые получил \(i\)-й парламентарий.
В первой строке выходного файла выведите «YES», если можно таким образом назначить каждому парламентарию его партию, и выбрать, за кого он проголосовал, чтобы список, полученный Скруджем, оказался корректен, и «NO» в противном случае.
Если искомое назначение существует, то во второй строке выведите \(n\) целых чисел — 1, если \(i\)-й политик состоит в партии Даков, или 2, если он состоит в партии Маусов.
5 1 2 0 2 0
YES 1 1 2 2 2
Первая группа тестов состоит из тестов, для которых выполняется ограничение \(1 \le n \le 15\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение \(1 \le n \le 300\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
Третья группа тестов состоит из тестов, для которых выполняется ограничение \(1 \le n \le 100\,000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.