CF1794C.Scoring Subsequences

The score of a sequence $[s_1, s_2, \ldots, s_d]$ is defined as $\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$ , where $d!=1\cdot 2\cdot \ldots \cdot d$ . In particular, the score of an empty sequence is $1$ .

For a sequence $[s_1, s_2, \ldots, s_d]$ , let $m$ be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of $m$ .

You are given a non-decreasing sequence $[a_1, a_2, \ldots, a_n]$ of integers of length $n$ . In other words, the condition $a_1 \leq a_2 \leq \ldots \leq a_n$ is satisfied. For each $k=1, 2, \ldots , n$ , find the cost of the sequence $[a_1, a_2, \ldots , a_k]$ .

A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements.

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 an integer $n$ ( $1\le n\le 10^5$ ) — the length of the given sequence.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $1\le a_i\leq n$ ) — the given sequence. It is guaranteed that its elements are in non-decreasing order.

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

For each test case, output $n$ integers — the costs of sequences $[a_1, a_2, \ldots , a_k]$ in ascending order of $k$ .

In the first test case:

• The maximum score among the subsequences of $[1]$ is $1$ . The subsequences $[1]$ and $[]$ (the empty sequence) are the only ones with this score. Thus, the cost of $[1]$ is $1$ .
• The maximum score among the subsequences of $[1, 2]$ is $2$ . The only subsequence with this score is $[2]$ . Thus, the cost of $[1, 2]$ is $1$ .
• The maximum score among the subsequences of $[1, 2, 3]$ is $3$ . The subsequences $[2, 3]$ and $[3]$ are the only ones with this score. Thus, the cost of $[1, 2, 3]$ is $2$ .

Therefore, the answer to this case is $1\:\:1\:\:2$ , which are the costs of $[1], [1, 2]$ and $[1, 2, 3]$ in this order.