수열 \(A\)가 주어졌을 때, 가장 긴 바이토닉 부분 수열(Longest Bitonic Subsequence)의 길이를 구하는 프로그램을 작성하시오.

바이토닉 부분 수열의 정의

수열 \(A=(a_1,a_2,\dots,a_N)\)에서 일부 원소를 원래 순서대로 골라 만든 수열을 \(B=(b_1,b_2,\dots,b_k)\)라고 하자.

\(B\)가 다음 조건을 만족하면 바이토닉 부분 수열이라고 한다.

• 어떤 위치 \(t\)가 존재하여 \(b_1<b_2<\dots<b_t\)이고 \(b_t>b_{t+1}>\dots>b_k\)이다.

선택한 원소들이 원래 수열에서 서로 연속해 있을 필요는 없다. 증가하는 부분과 감소하는 부분은 모두 엄격해야 하므로 값이 같은 두 원소를 이어서 선택할 수 없다.

\(t=1\)이면 증가하는 부분이 첫 원소 하나뿐인 감소 수열이 되고, \(t=k\)이면 감소하는 부분이 마지막 원소 하나뿐인 증가 수열이 된다. 따라서 원소 하나로 이루어진 수열, 엄격하게 증가하기만 하는 수열, 엄격하게 감소하기만 하는 수열도 모두 바이토닉 수열이다.

예를 들어, \(\{1,5,2,4,3,2,1\}\)에서 \(\{1,2,4,3,2,1\}\)은 \(4\)까지 증가한 뒤 감소하는 바이토닉 부분 수열이다.

입력

첫째 줄에 수열 \(A\)의 크기 \(N\)이 주어진다.

둘째 줄에 수열 \(A\)를 이루는 \(A_i\)가 순서대로 주어진다.

출력

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

제한 사항

• \(1 \le N \le 1,000\)
• \(1 \le A_i \le 1,000\)

예제 입력 1

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

예제 설명 1

\(\{1,2,3,4,5,2,1\}\)을 선택하면 길이가 \(7\)인 바이토닉 부분 수열을 만들 수 있다.