Scoring Subsequences
Contest: Codeforces Round 856 (Div. 2)
Difficulty rating: 1300
Tags: binary search, greedy, math, two pointers

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

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

Example input:
3
3
1 2 3
2
1 1
5
5 5 5 5 5

Example output:
1 1 2 
1 1 
1 2 3 4 5

Editorial:
We will first see how to find the cost of a single non-decreasing sequence $$$s_1, s_2, \ldots, s_\ell$$$.
If we choose a subsequence with $$$k$$$ elements, to achieve the maximum score it is optimal to choose the $$$k$$$ largest elements. As the sequence is in non-decreasing order, the $$$k$$$ largest elements will be the last $$$k$$$ elements of the sequence. Thus, all possible candidates to be the answer are the suffixes of the sequence.
Now let's divide the $$$i$$$-th element from the right by $$$i$$$. The sequence now turns into $$$\displaystyle \frac{s_1}{\ell}, \frac{s_2}{\ell-1}, \ldots, \frac{s_{\ell-1}}{2}, \frac{s_\ell}{1}$$$. Observe that the score of a suffix in the original sequence is equal to the product of the suffix of the same size in the new sequence.
The original sequence satisfies $$$s_1 \leq s_2 \leq \ldots \leq s_{\ell-1} \leq s_\ell$$$. It also true that $$$\displaystyle \frac{1}{\ell} \leq \frac{1}{\ell-1} \leq \ldots \leq \frac{1}{2} \leq \frac{1}{1}$$$ then combining these two inequalities we have $$$\displaystyle \frac{s_1}{\ell} \leq \frac{s_2}{\ell-1} \leq \ldots \leq \frac{s_{\ell-1}}{2} \leq \frac{s_\ell}{1}$$$ so the new sequence is also in non-decreasing order.
In order to maximize the product of a suffix in the new sequence, we will choose all the elements in the new sequence which are greater or equal to $$$1$$$ (these elements form a suffix because the new sequence is non-decreasing). If there are elements equal to $$$1$$$ in the new sequence, we have to choose them in order to get the subsquence with maximum length (among all the ones with maximum score).
Therefore, the cost of a sequence $$$s_1, s_2, \ldots, s_\ell$$$ is the maximum length of a suffix of $$$\displaystyle \frac{s_1}{\ell}, \frac{s_2}{\ell-1}, \ldots, \frac{s_{\ell-1}}{2}, \frac{s_\ell}{1}$$$ such that each element is at least $$$1$$$.
Now, we have to find the cost of every prefix of the given sequence $$$[a_1, a_2, \ldots , a_n]$$$. For a fixed $$$k$$$, the cost of $$$[a_1, a_2, \ldots , a_k]$$$ will be the maximum length of a suffix of $$$\displaystyle \frac{a_1}{k}, \frac{a_2}{k-1}, \ldots, \frac{a_{k-1}}{2}, \frac{a_k}{1}$$$ such that each element is at least $$$1$$$. We can find this length using binary search. Observe that we cannot compute the transformed sequence for every prefix, as that will be too slow. Instead, we can compute in each step of the binary search what would the number in that position be in the transformed sequence. By doing these, we can find the score of each prefix in $$$\mathcal{O}(\text{log}\:n)$$$ time.
Intended complexity: $$$\mathcal{O}(n\:\text{log}\:n)$$$ per test case.