Были заданы две последовательности — одна из них была строго возрастающей, а другая — строго убывающей.
Строго возрастающая последовательность — это последовательность целых чисел \([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».
Выходные данные
Если входные данные противоречивы и невозможно разбить заданную последовательность \(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»).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
7 2 7 3 3 1 4
|
YES
2
3 7
5
7 4 3 2 1
|
|
2
|
5
4 3 1 5 3
|
YES
1
3
4
5 4 3 1
|
|
3
|
5
1 1 2 1 2
|
NO
|
|
4
|
5
0 1 2 3 4
|
YES
0
5
4 3 2 1 0
|