| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem C
Deleting Sequence
Time Limit: 1000ms
Memory Limit: 65536kb Description
There is a sequence with its length N in Dreamone’s hands. Now he wants to delete some numbers to make the i-th number exactly equal to i as much as possible.
For example, there exists five numbers: 1 1 2 5 4 .After deleting the first numbers 1, the new sequence is 1 2 5 4. In this new sequence, we see the first number is 1, the second number is 2 and the fourth number is 4. So the answer is 3.
Input
The first line, an integer T, representing T test cases below. (T<=10).For each case: a number N, representing the length of the sequence (1<=N<=500000), followed by N integers. Output
For each case, output the answer.
Sample Input
2 5 1 1 2 5 4 4 1 2 3 4 Sample Output
3 4 |