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.