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.

序列 $[s_1, s_2, \ldots, s_d]$ 的得分定义为 $\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$，其中 $d!=1\cdot 2\cdot \ldots \cdot d$。特别地，空序列的得分为 $1$。

对于序列 $[s_1, s_2, \ldots, s_d]$，设 $m$ 为其所有子序列中得分的最大值，则该序列的代价定义为：所有得分等于 $m$ 的子序列中的最大长度。

给定一个长度为 $n$ 的非递减整数序列 $[a_1, a_2, \ldots, a_n]$，即满足 $a_1 \leq a_2 \leq \ldots \leq a_n$。对每个 $k = 1, 2, \ldots, n$，求序列 $[a_1, a_2, \ldots, a_k]$ 的代价。

若序列 $x$ 可通过从序列 $y$ 中删除若干（可能为零个或全部）元素得到，则称 $x$ 是 $y$ 的一个子序列。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^5$）—— 给定序列的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\leq n$）—— 给定序列。保证其元素按非递减顺序排列。

保证所有测试用例的 $n$ 之和不超过 $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$.

对于每个测试用例，输出 $n$ 个整数——即序列 $[a_1, a_2, \ldots , a_k]$ 的代价，按 $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.

在第一个测试用例中：

• 子序列 $[1]$ 的子序列中最大得分为 $1$。只有子序列 $[1]$ 和 $[]$（空序列）具有该得分。因此，$[1]$ 的代价为 $1$。
• 子序列 $[1, 2]$ 的子序列中最大得分为 $2$。唯一具有该得分的子序列是 $[2]$。因此，$[1, 2]$ 的代价为 $1$。
• 子序列 $[1, 2, 3]$ 的子序列中最大得分为 $3$。只有子序列 $[2, 3]$ 和 $[3]$ 具有该得分。因此，$[1, 2, 3]$ 的代价为 $2$。

因此，本测试用例的答案为 $1\:\:1\:\:2$，即按顺序给出的 $[1]$、$[1, 2]$ 和 $[1, 2, 3]$ 的代价。