Bipartite Array

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 个整数 $1, 2, \dots, n$ 组成的排列 $p$（排列是一个数组，其中每个 $1$ 到 $n$ 的元素恰好出现一次）。

我们称一个数组 $a$ 是二分的，如果如下无向图是二分图：

• 图包含 $n$ 个顶点；
• 当 $i < j$ 且 $a_i > a_j$ 时，顶点 $i$ 和 $j$ 之间有一条边。

你的任务是找到一个大小为 $n$ 的整数数组 $a$，使得 $a_i = p_i$ 或 $a_i = -p_i$，并且 $a$ 是二分的，或者报告不存在这样的数组。如果有多个答案，输出任意一个即可。

输入格式

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

样例输入 1

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

样例输出 1

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

数据范围

$1\le t\le2\cdot10^5$，$1\le n\le10^6$，每个 $p$ 均为 $1$ 到 $n$ 的排列，且所有测试用例的 $n$ 之和不超过 $10^6$。