CF1794C.Scoring Subsequences
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The score of a sequence [s1,s2,…,sd] is defined as d!s1⋅s2⋅…⋅sd , where d!=1⋅2⋅…⋅d . In particular, the score of an empty sequence is 1 .
For a sequence [s1,s2,…,sd] , 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] of integers of length n . In other words, the condition a1≤a2≤…≤an is satisfied. For each k=1,2,…,n , find the cost of the sequence [a1,a2,…,ak] .
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≤t≤104 ). The description of the test cases follows.
The first line of each test case contains an integer n ( 1≤n≤105 ) — the length of the given sequence.
The second line of each test case contains n integers a1,a2,…,an ( 1≤ai≤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⋅105 .
输出格式
For each test case, output n integers — the costs of sequences [a1,a2,…,ak] in ascending order of k .
输入输出样例
输入#1
3 3 1 2 3 2 1 1 5 5 5 5 5 5
输出#1
1 1 2 1 1 1 2 3 4 5
说明/提示
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 112 , which are the costs of [1],[1,2] and [1,2,3] in this order.