A14854 | Bipartite Array

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.

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$ .

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.