310571: CF1853D. Imbalanced Arrays

D. Imbalanced Arraystime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Ntarsis has come up with an array $a$ of $n$ non-negative integers.

Call an array $b$ of $n$ integers imbalanced if it satisfies the following:

• $-n\le b_i\le n$, $b_i \ne 0$,
• there are no two indices $(i, j)$ ($1 \le i, j \le n$) such that $b_i + b_j = 0$,
• for each $1 \leq i \leq n$, there are exactly $a_i$ indices $j$ ($1 \le j \le n$) such that $b_i+b_j>0$, where $i$ and $j$ are not necessarily distinct.

Given the array $a$, Ntarsis wants you to construct some imbalanced array. Help him solve this task, or determine it is impossible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case has a single integer $n$ ($1 \leq n \leq 10^5$).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

Output

For each test case, output "NO" if there exists no imbalanced array.

Otherwise, output "YES". Then, on the next line, output $n$ integers $b_1, b_2, \ldots, b_n$ where $b_i \neq 0$ for all $1 \leq i \leq n$ — an imbalanced array.

ExampleInput

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

Output

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

Note

For the first test case, $b = [1]$ is an imbalanced array. This is because for $i = 1$, there is exactly one $j$ ($j = 1$) where $b_1 + b_j > 0$.

For the second test case, it can be shown that there exists no imbalanced array.

For the third test case, $a = [0, 1, 0]$. The array $b = [-3, 1, -2]$ is an imbalanced array.

• For $i = 1$ and $i = 3$, there exists no index $j$ such that $b_i + b_j > 0$.
• For $i = 2$, there is only one index $j = 2$ such that $b_i + b_j > 0$ ($b_2 + b_2 = 1 + 1 = 2$).

Another possible output for the third test case could be $b = [-2, 1, -3]$.

题目大意：
Ntarsis有一个由n个非负整数组成的数组a。称一个由n个整数组成的数组b为不平衡的，如果它满足以下条件：
- $-n \leq b_i \leq n$，$b_i \neq 0$，
- 不存在两个索引$(i, j)$（$1 \leq i, j \leq n$）使得$b_i + b_j = 0$，
- 对于每个$1 \leq i \leq n$，恰好有$a_i$个索引$j$（$1 \leq j \leq n$）使得$b_i + b_j > 0$，其中$i$和$j$不一定不同。

给定数组a，Ntarsis想要你构建一个不平衡数组。帮助他完成这个任务，或者确定这是不可能的。

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例数$t$（$1 \leq t \leq 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$，其中对于所有$1 \leq i \leq n$，$b_i \neq 0$——一个不平衡数组。题目大意： Ntarsis有一个由n个非负整数组成的数组a。称一个由n个整数组成的数组b为不平衡的，如果它满足以下条件： - $-n \leq b_i \leq n$，$b_i \neq 0$， - 不存在两个索引$(i, j)$（$1 \leq i, j \leq n$）使得$b_i + b_j = 0$， - 对于每个$1 \leq i \leq n$，恰好有$a_i$个索引$j$（$1 \leq j \leq n$）使得$b_i + b_j > 0$，其中$i$和$j$不一定不同。 给定数组a，Ntarsis想要你构建一个不平衡数组。帮助他完成这个任务，或者确定这是不可能的。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例数$t$（$1 \leq t \leq 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$，其中对于所有$1 \leq i \leq n$，$b_i \neq 0$——一个不平衡数组。