← 返回题目列表

Codeforces · 1620/F

F. 二分数组

中文机器翻译题面 查看原题

给你一个排列 $$$p$$$,由 $$$n$$$ 整数 $$$1, 2, \dots, n$$$ 组成(排列是一个数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素只出现一次)。

如果以下无向图是二分图,我们将数组 $$$a$$$ 称为二分数组:

- 该图由 $$$n$$$ 个顶点组成;
- 如果 $$$i < j$$$ 且 $$$a_i > a_j$$$,则两个顶点 $$$i$$$ 和 $$$j$$$ 通过边连接。

你的任务是找到一个大小为 $$$n$$$ 的整数二分数组 $$$a$$$,使得 $$$a_i = p_i$$$ 或 $$$a_i = -p_i$$$,或者报告不存在这样的数组。如果有多个答案,请打印其中任何一个。

输入

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