가장 긴 바이토닉 부분 수열

수열 A가 주어질 때 가장 긴 바이토닉 부분 수열의 길이를 구하라.

바이토닉 수열이란 어떤 위치 k를 기준으로 A[1] < A[2] < ... < A[k] > A[k+1] > ... > A[n]을 만족하는 수열이다. 즉 순증가 구간 뒤에 순감소 구간이 오는 형태이다. 증가 구간 또는 감소 구간 중 하나만 있어도 바이토닉 수열로 본다.

부분 수열은 원래 수열에서 순서를 유지하며 일부 원소를 제거해 만든다.

입력

첫째 줄에 수열의 크기 N이 주어진다.
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

• 1 ≤ N ≤ 1,000
• 1 ≤ 각 정수 ≤ 1,000

출력

가장 긴 바이토닉 부분 수열의 길이를 출력한다.

예제 입력 1

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1

7