Bipartite Array

2000ms

262144K

Description:

You are given a permutation $$$p$$$ consisting of $$$n$$$ integers $$$1, 2, \dots, n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once).

Let's call an array $$$a$$$ bipartite if the following undirected graph is bipartite:

the graph consists of $$$n$$$ vertices;
two vertices $$$i$$$ and $$$j$$$ are connected by an edge if $$$i < j$$$ and $$$a_i > a_j$$$.

Your task is to find a bipartite array of integers $$$a$$$ of size $$$n$$$, such that $$$a_i = p_i$$$ or $$$a_i = -p_i$$$, or report that no such array exists. If there are multiple answers, print any of them.

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$.

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output:

For each test case, print the answer in the following format. If such an array $$$a$$$ does not exist, print "NO" in a single line. Otherwise, print "YES" in the first line and $$$n$$$ integers — array $$$a$$$ in the second line.

Sample Input:

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

Sample Output:

YES
1 2 3
NO
YES
-4 -1 -3 -2
YES
-3 -2 1 6 7 -8 -5 -4

Informação

Provedor Codeforces

Código CF1620F