← 返回题目列表

Codeforces · 1852/B

B. 不平衡阵列

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

Ntarsis 提出了一个包含 $$$n$$$ 非负整数的数组 $$$a$$$。

如果满足以下条件,则调用由 $$$n$$$ 整数组成的数组 $$$b$$$ 不平衡:

- $$$-n\le b_i\le n$$$, $$$b_i \ne 0$$$,
- 不存在两个索引 $$$(i, j)$$$ ($$$1 \le i, j \le n$$$) 使得 $$$b_i + b_j = 0$$$,
- 对于每个 $$$1 \leq i \leq n$$$,恰好有 $$$a_i$$$ 索引 $$$j$$$ ($$$1 \le j \le n$$$) 使得 $$$b_i+b_j>0$$$,其中 $$$i$$$ 和 $$$j$$$ 不一定不同。

给定数组 $$$a$$$,Ntarsis 希望您构建一些不平衡数组。帮助他解决这个任务,或者确定这是不可能的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行都有一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果不存在不平衡数组,则输出“NO”。

否则,输出“YES”。然后,在下一行,输出 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$,其中 $$$b_i \neq 0$$$ 对于所有 $$$1 \leq i \leq n$$$ — 一个不平衡数组。

示例

输入 #1

5
1
1
4
1 4 3 4
3
0 1 0
4
4 3 2 1
3
1 3 1

输出 #1

YES
1 
NO
YES
-3 1 -2 
YES
4 2 -1 -3 
YES
-1 3 -1

注意

对于第一个测试用例,$$$b = [1]$$$ 是一个不平衡数组。这是因为对于 $$$i = 1$$$,恰好存在一个 $$$j$$$ ($$$j = 1$$$),其中 $$$b_1 + b_j > 0$$$。

对于第二个测试用例,可以证明不存在不平衡阵列。

对于第三个测试用例,$$$a = [0, 1, 0]$$$。数组 $$$b = [-3, 1, -2]$$$ 是一个不平衡数组。

- 对于 $$$i = 1$$$ 和 $$$i = 3$$$,不存在使得 $$$b_i + b_j > 0$$$ 的索引 $$$j$$$。
- 对于 $$$i = 2$$$,只有一个索引 $$$j = 2$$$ 使得 $$$b_i + b_j > 0$$$ ($$$b_2 + b_2 = 1 + 1 = 2$$$)。