Clan War Map — Supercell, Clash of Clans

This is the constructive version of the problem. The difference between the versions is that in this version, you need to either construct an answer or report that it is impossible, and $$$0 \leq b_i \leq 10^9$$$. You can hack only if you solved all versions of this problem.

The Master Builder doesn't like repetitive tasks — repairing the base, upgrading the town hall fifteen times, and doing yet more programming problems about MEX. So, this is not going to be your ordinary MEX problem.

For any positive integer $$$k$$$, define the $$$k$$$-mex of a collection of integers $$$S$$$ to be the $$$k$$$-th smallest nonnegative integer not present in $$$S$$$. For instance, the $$$1$$$-mex and $$$2$$$-mex of $$$[1, 2, 1]$$$ are $$$0$$$ and $$$3$$$, respectively.

Let $$$n$$$ be a positive integer, and consider an array of nonnegative integers $$$[a_1, \ldots, a_n]$$$. Determine whether or not there exists an array of nonnegative integers $$$[b_1, \ldots, b_n]$$$ such that:

For all $$$1 \leq i \leq n$$$, the $$$(n-i+1)$$$-mex of $$$[b_1, \ldots, b_i]$$$ is $$$a_i$$$.

Additionally, if such an array $$$b$$$ exists, find any such $$$[b_1, \ldots, b_n]$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a line containing either "YES" or "NO", representing whether or not the array $$$b$$$ exists. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Then, if you responded with "YES", print a second line containing $$$n$$$ integers $$$b_1, \ldots, b_n$$$ ($$$0 \leq b_i \leq 10^9$$$) such that for all $$$1 \leq i \leq n$$$, the $$$(n-i+1)$$$-mex of $$$[b_1, \ldots, b_i]$$$ is $$$a_i$$$.

Note

In the first test case, the array $$$a = [3, 3, 1]$$$. We can check that the array $$$b = [2, 0, 2]$$$ satisfies the conditions because:

the $$$3$$$-mex of $$$[b_1] = [2]$$$ is $$$a_1 = 3$$$,
the $$$2$$$-mex of $$$[b_1, b_2] = [2, 0]$$$ is $$$a_2 = 3$$$,
the $$$1$$$-mex of $$$[b_1, b_2, b_3] = [2, 0, 2]$$$ is $$$a_3 = 1$$$.

In the second test case, the array $$$a = [2, 1, 3]$$$. It can be shown that no suitable array $$$b$$$ exists.

In the third test case, the array $$$a = [0]$$$. We can check that the array $$$b = [67]$$$ satisfies the conditions because the $$$1$$$-mex of $$$[b_1] = [67]$$$ is $$$a_1 = 0$$$.

N-MEX (Constructive Version)

Examples