Description
N명의 고객이 우체국에서 소포를 받기 위해 줄을 서서 기다리고 있다. 소포는 우체국에 하나씩 도착하는데 단순화를 위해, 소포가 도착하는 순서대로 소포에 1부터 N까지 번호를 붙인다. 각 고객은 우체국에서 소포 하나를 받으려고 줄을 서는데 줄에서 K번째 고객(여기서 K는 0부터 N-1까지)은 client[K]번 소포를 받으려고 한다. 이때, 소포가 도착한 후에는 다음 중 하나의 일이 발생한다.
-
줄의 맨 앞 고객이 자기 소포를 받게되면 고객은 그 소포를 받고 줄에서 나가고, 그렇지 않은 경우에는 그 소포는 선반에 올려 놓는다.
-
만약 줄의 맨 앞 고객이 선반에 있는 소포를 받으려고 한다면, 그 고객은 줄에서 나가 해당 소포를 가져간다.
여기서 주의할 점은, 줄의 맨 앞에 있는 고객만 자신의 소포를 받을 수 있다는 것이다. 이러한 방식으로 처리가 이루어질 경우에 동시에 선반에 보관되는 소포는 최대 몇 개일까?
예를 들어 client[5] = {3, 2, 4, 5, 1} 이라고 하면 다음과 같이 처리가 이루어진다.
-
첫 번째 고객은 3번 소포를 기다리므로, 1번과 2번 소포는 선반에 놓인다.
-
3번 소포가 도착하면 첫 번째 고객이 그것을 가져간다.
-
두 번째 고객은 선반에 있던 2번 소포를 가져간다.
-
세 번째와 네 번째 고객은 각각 4번과 5번 소포를 기다리고, 해당 소포가 도착하자마자 가져간다.
-
마지막 고객은 선반에 있던 1번 소포를 가져간다.
따라서 이 경우 동시에 선반에 보관된 소포의 최대 개수는 2이다.
Input
첫 줄에 테스트케이스의 개수(t)가 입력된다.( 1 <= t <= 10 )
다음 줄에는 고객수가 주어지고 다음다음 줄에 받으려는 소포의 번호가 순서대로 주어진다. 고객수가 N인 경우 소포 번호는 0부터 N-1까지로 중복되지 않는다(1 <= N <= 1,000). 이 두 줄이 테스트케이스의 개수만큼 반복된다.
Output
각 테스트케이스에 대하여 동시에 선반에 보관되는 소포의 최대 개수를 한 줄에 하나씩 출력한다.
3
5
3 2 4 5 1
7
3 2 7 5 4 1 6
5
1 2 3 4 5