CF1930C.Lexicographically Largest

Stack has an array $a$ of length $n$ . He also has an empty set $S$ . Note that $S$ is not a multiset.

He will do the following three-step operation exactly $n$ times:

1. Select an index $i$ such that $1 \leq i \leq |a|$ .
2. Insert $^\dagger$ $a_i + i$ into $S$ .
3. Delete $a_i$ from $a$ . Note that the indices of all elements to the right of $a_i$ will decrease by $1$ .

Note that after $n$ operations, $a$ will be empty.

Stack will now construct a new array $b$ which is $S$ sorted in decreasing order. Formally, $b$ is an array of size $|S|$ where $b_i$ is the $i$ -th largest element of $S$ for all $1 \leq i \leq |S|$ .

Find the lexicographically largest $^\ddagger$ $b$ that Stack can make.

$^\dagger$ A set can only contain unique elements. Inserting an element that is already present in a set will not change the elements of the set.

$^\ddagger$ An array $p$ is lexicographically larger than a sequence $q$ if and only if one of the following holds:

• $q$ is a prefix of $p$ , but $p \ne q$ ; or
• in the first position where $p$ and $q$ differ, the array $p$ has a larger element than the corresponding element in $q$ .

Note that $[3,1,4,1,5]$ is lexicographically larger than $[3,1,3]$ , $[\,]$ , and $[3,1,4,1]$ but not $[3,1,4,1,5,9]$ , $[3,1,4,1,5]$ , and $[4]$ .

Each test contains multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_{n}$ ( $1 \leq a_i \leq 10^9$ ) — the elements of array $a$ .

The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .

For each test case, output the lexicographically largest $b$ .

In the first test case, select $i=1$ in the first operation, insert $a_1 + 1 = 3$ in $S$ , and delete $a_1$ from $a$ . After the first operation, $a$ becomes $a=[1]$ . In the second operation, we select $i=1$ again and insert $a_1 + 1 = 2$ in $S$ . Thus $S=\{2, 3\}$ , and $b = [3, 2]$ .

Note that if you select $i=2$ in the first operation, and $i=1$ in the second operation, $S=\{3\}$ as $3$ will be inserted twice, resulting in $b=[3]$ .

As $[3,2]$ is lexicographically larger than $[3]$ , we should select $i=1$ in the first operation.

In the second test case, in each operation, select the last element.