排列

题目描述:

染染有一个长度为 \(n\) 的排列 \(1,2,\cdots, n\)，他将这个排列重排并给其中几个数加上了负号得到了序列 \(a_1,a_2,\cdots,a_n\)。换句话说，\(a_1,a_2,\cdots,a_n\) 是满足如下条件的整数序列：

+ 任意的 \(a_i\) 的绝对值都是大于等于 \(1\) 小于等于 \(n\) 的整数。
+ 对于任意的 \(i\) 不等于 \(j\)，都满足 \(a_i\) 的绝对值都不等于 \(a_j\) 的绝对值。

其中，我们称 \(|x|\) 为 \(x\) 的绝对值，当 \(x\ge0\) 则 \(|x|=x\)，否则当 \(x<0\) 则 \(|x|=-x\)。

现在染染对这个序列生成了另一个序列 \(b_1,b_2,\cdots ,b_n\)，其中 \(b_i\) 是满足 \(a_i+a_j>0\) 的 \(j\) 的数量。

不幸的是，染染忘记了序列 \(a_1,a_2,\cdots,a_n\)，只是模糊记得生成的序列 \(b_1,b_2,\cdots,b_n\)，你可以帮他判定这个序列 \(b_1,b_2,\cdots,b_n\) 是否正确吗？换句话说，序列 \(b_1,b_2,\cdots,b_n\) 有对应的序列 \(a_1,a_2,\cdots,a_n\) 吗？如果正确，可以帮他找到一个对应的序列 \(a_1,a_2,\cdots,a_n\) 吗？

输入格式:

第一行一个整数 \(T\,\,(1\leq T\leq 10^6)\)，表示数据组数.

对于每组数据，第一行一个整数 \(n\,\,(1\leq n\leq 10^6)\)，表示序列长度。

第二行 \(n\) 个整数 \(b_1,b_2,\cdots ,b_n\,\,(0\leq b_i\leq n)\)，表示序列。

保证单个测试点中所有数据的 \(n\) 的和不超过 \(10^6\)。

输出格式:

对于每组数据，输出第一行一个字符串 \(\texttt{YES}\) 或 \(\texttt{NO}\)，表示输入的序列 \(b_1,b_2,\cdots b_n\) 正确或不正确。

如果第一行输出 \(\texttt{YES}\)，那么第二行输出对应的序列 \(a_1,a_2,\cdots,a_n\)，否则没有第二行输出。

如果有多组合法的序列 \(a_1,a_2,\cdots a_n\)，只需要输出其中一种即可。

数据范围:

- 对于 \(30\%\) 的数据有：\(n\le 7\)，\(n\) 的总和不超过 \(1000\)。
- 对于 \(60\%\) 的数据有：\(n\le 1000\)，\(n\) 的总和不超过 \(10^4\)。
- 对于 \(80\%\) 的数据有：\(n\le 10^5\)，\(n\) 的总和不超过 \(10^6\)。
- 对于 \(100\%\) 的数据有：\(n\le 10^6\)，\(n\) 的总和不超过 \(10^6\)。

样例输入:

3
3
3 3 3
3
1 1 1
5
3 2 2 5 5

样例输出:

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

时间限制: 1000ms
空间限制: 512MB

---