Были заданы две последовательности — одна из них была строго возрастающей, а другая — строго убывающей.
Строго возрастающая последовательность — это последовательность целых чисел [x1<x2<⋯<xk]. А строго убывающая последовательность — это последовательность целых чисел [y1>y2>⋯>yl]. Заметьте, что пустая последовательность и последовательность, состоящая из одного элемента, могут являться как возрастающими, так и убывающими.
Они были объединены в одну последовательность 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≤n≤2⋅105) — количество элементов в a.
Вторая строка входных данных содержит n целых чисел a1,a2,…,an (0≤ai≤2⋅105), где ai — i-й элемент a.
Если входные данные противоречивы и невозможно разбить заданную последовательность a на убывающую и возрастающую последовательности, выведите «NO» в первой строке.
Иначе выведите «YES» в первой строке и любые две подходящие последовательности. Заметьте, что пустая последовательность и последовательность, состоящая из одного элемента, могут являться как возрастающими, так и убывающими.
Во второй строке выведите ni — количество элементов в строго возрастающей последовательности. ni может быть равно нулю, в том случае возрастающая последовательность пуста.
В третьей строке выведите ni целых чисел inc1,inc2,…,incni в возрастающем порядке их значений (inc1<inc2<⋯<incni) — строго возрастающую последовательность. Вы можете оставить эту строку пустой, если ni=0 (или просто вывести пустую строку).
В четвертой строке выведите nd — количество элементов в строго убывающей последовательности. nd может быть равно нулю, в том случае возрастающая последовательность пуста.
В пятой строке выведите nd целых чисел dec1,dec2,…,decnd в убывающем порядке их значений (dec1>dec2>⋯>decnd) — строго убывающую последовательность. Вы можете оставить эту строку пустой, если nd=0 (или просто вывести пустую строку).
ni+nd должны быть равны 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) |
|---|
| Закончено |
