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
© 2015 HUST ACMICPC TEAM. All Right Reserved.