시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 7 7 6 100.000%

문제

1부터 n까지 정수 n개로 이루어진 길이가 n인 수열 A가 있다. 수열의 각 원소는 서로 다르다. 이 때, 다음과 같은 조건을 만족하는 수열 B를 찾으려고 한다.

B[0] > B[1] < B[2] > B[3] < ...

B는 A의 부분 수열이고, 위의 조건을 만족하는 수열 중 가장 길이가 긴 수열이다. 부분 수열이란 수열에서 원소 몇 개를 삭제해서 얻을 수 있는 수열이다. 이 때, 순서는 항상 유지되어야 한다.

A가 주어졌을 때, B의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 50이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 다음과 같은 형식이다.

n A[0] A[1] A[2] ... A[n-1]

n은 최대 30000이다. 

출력

각 테스트 케이스에 대해서, B의 길이를 출력한다. 

예제 입력

4
5 1 2 3 4 5
5 5 4 3 2 1
5 5 1 4 2 3
5 2 4 1 3 5

예제 출력

1
2
5
3

힌트