After practicing Fillomino skills, Little Cyan Fish decides to train more on the game "The Artisan of Glimmith".

Little Cyan Fish first introduces the rules of Fillomino to you:

For a rectangle of $m$ rows and $n$ columns, divide the grid into several regions (the cells of each region must be orthogonally connected), such that any two adjacent regions have different areas. Some cells in the grid already have numbers filled in. The number indicates the area of the region it belongs to.

An example of a Fillomino puzzle. Source: Puzzle GP 2022 R4

Little Cyan Fish now gives you a Fillomino board, and he wants to construct any valid solution for this Fillomino puzzle.

Of course, this problem is too difficult for Little Cyan Fish, so you only need to solve the case where $m = 1$. In other words, given a row of $n$ cells, you want to divide these cells into several segments (each segment completely contains several consecutive cells), requiring that:

• Any two adjacent segments have different lengths;
• Some cells contain some numbers, and these numbers indicate the number of cells in the segment to which this cell belongs.

Little Cyan Fish asks you to determine whether there exists a valid solution for the board. If it exists, you also need to output any valid solution.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line of the input contains an integer $n$ ($1 \le n \le 10^6$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$). If $a_i = 0$, it means no number is filled in the $i$-th cell. Otherwise, it means $a_i$ is filled in the $i$-th cell.

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

Output

For each test case, if there does not exist any valid scheme to fill the numbers, then output a single line "No".

Otherwise, the first line of the output contains the string "Yes". The next line outputs $n$ integers, representing the length of the segment where each cell is located in the scheme you constructed. If there are multiple schemes that meet the requirements, you can output any of them.

Example

Input 1

7
3
0 0 0
4
2 0 0 0
4
0 2 0 0
6
0 3 3 0 3 0
10
2 0 0 3 0 0 4 0 0 1
6
0 0 1 1 0 0
6
1 2 3 4 5 6

Output 1

Yes
2 2 1
No
Yes
1 2 2 1
No
Yes
2 2 3 3 3 4 4 4 4 1
No
No