Были заданы две последовательности — одна из них была строго возрастающей, а другая — строго убывающей.
Строго возрастающая последовательность — это последовательность целых чисел $$$[x_1 < x_2 < \dots < x_k]$$$. А строго убывающая последовательность — это последовательность целых чисел $$$[y_1 > y_2 > \dots > y_l]$$$. Заметьте, что пустая последовательность и последовательность, состоящая из одного элемента, могут являться как возрастающими, так и убывающими.
Они были объединены в одну последовательность $$$a$$$. После этого последовательность $$$a$$$ была перемешана. Например, некоторыми возможными результирующими последовательностями $$$a$$$ для возрастающей последовательности $$$[1, 3, 4]$$$ и убывающей последовательности $$$[10, 4, 2]$$$ являются последовательности $$$[1, 2, 3, 4, 4, 10]$$$ и $$$[4, 2, 1, 10, 4, 3]$$$.
Эта перемешанная последовательность $$$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_i$$$ — количество элементов в строго возрастающей последовательности. $$$n_i$$$ может быть равно нулю, в том случае возрастающая последовательность пуста.
В третьей строке выведите $$$n_i$$$ целых чисел $$$inc_1, inc_2, \dots, inc_{n_i}$$$ в возрастающем порядке их значений ($$$inc_1 < inc_2 < \dots < inc_{n_i}$$$) — строго возрастающую последовательность. Вы можете оставить эту строку пустой, если $$$n_i = 0$$$ (или просто вывести пустую строку).
В четвертой строке выведите $$$n_d$$$ — количество элементов в строго убывающей последовательности. $$$n_d$$$ может быть равно нулю, в том случае возрастающая последовательность пуста.
В пятой строке выведите $$$n_d$$$ целых чисел $$$dec_1, dec_2, \dots, dec_{n_d}$$$ в убывающем порядке их значений ($$$dec_1 > dec_2 > \dots > dec_{n_d}$$$) — строго убывающую последовательность. Вы можете оставить эту строку пустой, если $$$n_d = 0$$$ (или просто вывести пустую строку).
$$$n_i + n_d$$$ должны быть равны $$$n$$$, а объединение выведенных последовательностей должно быть перестановкой заданной последовательности (в случае ответа «YES»).
7 7 2 7 3 3 1 4
YES 2 3 7 5 7 4 3 2 1
5 4 3 1 5 3
YES 1 3 4 5 4 3 1
5 1 1 2 1 2
NO
5 0 1 2 3 4
YES 0 5 4 3 2 1 0
| Codeforces Round 550 (Div. 3) |
|---|
| Закончено |
