문제
증감 수열이란, 수열의 원소를 앞에서부터 고려할 때 증가/감소가 교차되는 수열을 의미한다(감소/증가로 시작해도 상관없다). 수학적으로 정의하면, 길이가 N인 수열 A[0...N-1] 가 증감 수열일 조건은 임의의 인덱스 i (0≤i≤N-2)에 대해 (A[i+1]-A[i])*(A[i+2]-A[i+1])<0 이다. 주어진 수열의 가능한 모든 부분 증감 수열들 가운데 가장 긴 것의 길이를 찾아라. 부분 수열이 연속된 원소로 구성될 필요는 없다.
입력
입력의 첫 행에는 수열의 길이 N (1≤N≤1000) 이 주어진다. 다음 N 개의 행에 걸쳐 한 행에 하나씩 수열의 원소가 차례로 주어진다. 각 원소는 -100 이상 100 이하이다.
출력
입력에 대해 부분 증감 수열의 최대 길이를 한 행에 하나씩 출력한다.
예제
4
1
5
3
-1
3
힌트
로그인해야 코드를 작성할 수 있어요.