G. Слияние двух последовательностей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас были две последовательности целых чисел, одна из которых была строго возрастающей, а другая — строго убывающей.

Строго возрастающая последовательность — это последовательность чисел $$$[x_1 < x_2 < \dots < x_k]$$$. А строго убывающая последовательность — это последовательность чисел $$$[y_1 > y_2 > \dots > y_l]$$$. Обратите внимание, что пустая последовательность и последовательность, состоящая из одного числа, тоже являются как строго возрастающими, так и строго убывающими последовательностями.

Элементы возрастающей последовательности вставили между элементами убывающей последовательности (и, возможно, перед первым элементом и после последнего) без изменения порядка элементов. Например, из последовательностей $$$[1, 3, 4]$$$ и $$$[10, 4, 2]$$$ можно составить одну из следующих последовательностей: $$$[10, \textbf{1}, \textbf{3}, 4, 2, \textbf{4}]$$$, $$$[\textbf{1}, \textbf{3}, \textbf{4}, 10, 4, 2]$$$. Следующая последовательность не может быть получена: $$$[\textbf{1}, 10, \textbf{4}, 4, \textbf{3}, 2]$$$, так как нельзя менять порядок элементов.

Пусть полученная последовательность — $$$a$$$. Эта последовательность $$$a$$$ задана во входных данных. Ваша задача — найти любую пару последовательностей, из которых она могла быть получена. Одна из этих последовательностей должна быть строго возрастающей, а другая — строго убывающей. Обратите внимание, что пустая последовательность и последовательность, состоящая из одного числа, тоже являются как строго возрастающими, так и строго убывающими последовательностями.

Если во входных данных есть противоречие и невозможно разбить $$$a$$$ на одну возрастающую и одну убывающую последовательность, выведите "NO".

Входные данные

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в $$$a$$$.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ — $$$i$$$-й элемент последовательности $$$a$$$.

Выходные данные

Если во входных данных есть противоречие и невозможно разбить $$$a$$$ на одну возрастающую и одну убывающую последовательность, выведите "NO" в первой строке.

Иначе в первой строке выведите "YES". Во второй строке выведите последовательность из $$$n$$$ целых чисел $$$res_1, res_2, \dots, res_n$$$, где $$$res_i$$$ должно быть равно либо $$$0$$$, либо $$$1$$$ для каждого $$$i$$$ от $$$1$$$ до $$$n$$$. $$$i$$$-й элемент этой последовательности должен быть равен $$$0$$$, если $$$i$$$-й элемент $$$a$$$ принадлежит к возрастающей последовательности, и $$$1$$$ в ином случае. Обратите внимание, что пустая последовательность и последовательность, состоящая из одного числа, тоже являются как строго возрастающими, так и строго убывающими последовательностями.

Примеры
Входные данные
9
5 1 3 6 8 2 9 0 10
Выходные данные
YES
1 0 0 0 0 1 0 1 0 
Входные данные
5
1 2 4 0 2
Выходные данные
NO