CF1620F Bipartite Array

给定一个由 $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$。

由 ChatGPT 4.1 翻译