1191 - SCU-K
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 134
Solved: 33
- Description
- A sequence is called "perfect" if and only if it contains
exactly 1,2,3,...n, and n is the length of the sequence.
So,{2,3,1} is a perfect sequence while {1,2,4} is not.
Now,consider a sequence {a[0],a[1]...a[n-1]},
it has many subsequence.
Some of the subsequence is perfect.
You need to find length of the longest perfect subsequence.
For example, the longest perfect subsequen of {1,2,5,3}
is {1,2},so your output should be 2. - Input
- The first line is a interger T, which is the number of
datasets that follow.
The length of the sequence n is in the first line of each
test case( 1 <= n <= 30000 ), followed by n possitive
integers which will between 1 and n.
- Output
- One line with the length of the longest perfect subsequence
for each test case. - sample input
-
3 5 1 3 4 1 2 6 6 2 1 3 4 1 3 1 5 2
- sample output
-
4 4 1
- hint
- source
- SCUPC