A11323 | 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$ .