CF1620F.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 \lt j$ and $a_i \gt 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.

给你一个由 $n$ 个整数 $1, 2, \dots, n$ 构成的排列 $p$（排列是指每个从 $1$ 到 $n$ 的整数恰好出现一次的数组）。

我们称一个整数数组 $a$ 是二分图的（bipartite），当且仅当如下无向图是二分图：

• 该图包含 $n$ 个顶点；
• 当且仅当 $i \lt j$ 且 $a_i \gt a_j$ 时，顶点 $i$ 与顶点 $j$ 之间存在一条边。

你的任务是：构造一个长度为 $n$ 的二分图数组 $a$，使得对每个 $i$，均有 $a_i = p_i$ 或 $a_i = -p_i$；若不存在这样的数组，则报告无解。若存在多个解，输出任意一个即可。

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

第一行包含一个整数 $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$。

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.

对于每个测试用例，按以下格式输出答案：如果不存在满足条件的数组 $a$，则在单独一行中输出 "NO"；否则，第一行输出 "YES"，第二行输出 $n$ 个整数 —— 即数组 $a$。