#1365 증감 수열

75  2 s   128 MB  

Description

증감 수열이란, 수열의 원소를 앞에서부터 고려할 때 증가/감소가 교차되는 수열을 의미한다 (감소/증가로 시작해도 상관없다).

주어진 수열의 가능한 모든 부분 증감 수열들 가운데 가장 긴 것의 길이를 찾아라. 부분 수열이 연속된 원소로 구성될 필요는 없다.

 

길이가 $N$인 수열 $A[0..N-1]$가 증감 수열일 조건은 임의의 인덱스 $i$ $(0 \leq i \le N - 2)$ 에 대해 수학적으로 정의하면 다음과 같다 :)

$(A[i + 1] - A[i]) * (A[i + 2] - A[i + 1]) \le 0$

(문제랑은 관련이 없음)

 

Input

첫 행에는 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 행에는 수열의 길이 $N (1 \leq N \leq 1000)$ 이 주어진다.

다음 $N$개의 행에 걸쳐 한 행에 하나씩 수열의 원소가 차례로 주어진다. 각 원소는 $-100$ 이상 $100$ 이하이다.

Output

 각 테스트 케이스에 대해 부분 증감 수열의 최대 길이를 한 행에 하나씩 출력한다.

Sample Input

Sample Output

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