Вам задана перестановка \(p\), состоящая из \(n\) чисел \(1, 2, \dots, n\) (перестановка — это массив, в котором каждый элемент от \(1\) до \(n\) встречается ровно один раз).
Назовем массив \(a\) двудольным, если следующий неориентированный граф является двудольным:
- граф состоит из \(n\) вершин;
- две вершины \(i\) и \(j\) соединены ребром, если \(i < j\) и \(a_i > a_j\).
Ваша задача — найти двудольный массив целых чисел \(a\) размера \(n\), такой что \(a_i = p_i\) или \(a_i = -p_i\), или сообщить, что такого массива не существует. Если существует несколько ответов, выведите любой из них.
Выходные данные
Для каждого набора входных данных выведите ответ в следующей формате. Если соответствующего массива \(a\) не существует, выведите «NO» в единственной строке. Иначе выведите «YES» в первой строке и \(n\) целых чисел — массив \(a\) во второй строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
6
1 3 2 6 5 4
4
4 1 3 2
8
3 2 1 6 7 8 5 4
|
YES
1 2 3
NO
YES
-4 -1 -3 -2
YES
-3 -2 1 6 7 -8 -5 -4
|