526互联

Scoring Subsequences

发布时间 2023-06-24 09:42:17作者: o-Sakurajimamai-o
Scoring Subsequences
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The score of a sequence [s1,s2,…,sd][1,2,…,] is defined as s1⋅s2⋅…⋅sdd!1⋅2⋅…⋅!, where d!=1⋅2⋅…⋅d!=1⋅2⋅…⋅. In particular, the score of an empty sequence is 11.

For a sequence [s1,s2,…,sd][1,2,…,], 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 [a1,a2,…,an][1,2,…,] of integers of length n. In other words, the condition a1≤a2≤…≤an1≤2≤…≤ is satisfied. For each k=1,2,…,n=1,2,…,, find the cost of the sequence [a1,a2,…,ak][1,2,…,].

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

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1041≤≤104). The description of the test cases follows.

The first line of each test case contains an integer n (1≤n≤1051≤≤105) — the length of the given sequence.

The second line of each test case contains n integers a1,a2,…,an1,2,…, (1≤ai≤n1≤≤) — 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⋅1055⋅105.

Output

For each test case, output n integers — the costs of sequences [a1,a2,…,ak][1,2,…,] in ascending order of k.

Example
input
Copy
3
3
1 2 3
2
1 1
5
5 5 5 5 5
output
Copy
1 1 2 
1 1 
1 2 3 4 5
Note

In the first test case:

  • The maximum score among the subsequences of [1][1] is 11. The subsequences [1][1] and [][] (the empty sequence) are the only ones with this score. Thus, the cost of [1][1] is 11.
  • The maximum score among the subsequences of [1,2][1,2] is 22. The only subsequence with this score is [2][2]. Thus, the cost of [1,2][1,2] is 11.
  • The maximum score among the subsequences of [1,2,3][1,2,3] is 33. The subsequences [2,3][2,3] and [3][3] are the only ones with this score. Thus, the cost of [1,2,3][1,2,3] is 22.
Therefore, the answer to this case is 112112, which are the costs of [1],[1,2][1],[1,2] and [1,2,3][1,2,3] in this order.
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans;
bool vis[N];
int op(int u)
{
    if(u==1||u==0) return 1;
    return u*op(u-1);
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        res=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            int l=1,r=i;
        //如果当前的数小于长度,那就肯定到不了最大值,所以求最小的当前值能让序列价值达到最大
        //二分即可
            while(l<r){
                int mid=l+r>>1;
                if(a[mid]>=i-mid+1) r=mid;
                else l=mid+1;
            }
            cout<<i-l+1<<" ";
        }
        cout<<endl;
    }
    return 0;
}