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

Вам задана перестановка $$$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$$$, или сообщить, что такого массива не существует. Если существует несколько ответов, выведите любой из них.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — размер перестановки.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

Для каждого набора входных данных выведите ответ в следующей формате. Если соответствующего массива $$$a$$$ не существует, выведите «NO» в единственной строке. Иначе выведите «YES» в первой строке и $$$n$$$ целых чисел — массив $$$a$$$ во второй строке.

Пример
Входные данные
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