가장 긴 바이토닉 부분 수열

수열 $S$가 어떤 원소 $S_k$를 기준으로 $S_1 < S_2 < \dots < S_{k-1} < S_k > S_{k+1} > \dots > S_{N-1} > S_N$을 만족하면 이 수열을 바이토닉 수열이라고 한다. 증가 구간과 감소 구간 중 한쪽이 비어 있어도 되므로, 순증가 수열과 순감소 수열도 바이토닉 수열이다.

예를 들어 {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10}은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30}은 바이토닉 수열이 아니다.

수열 $A$가 주어질 때, $A$의 부분 수열 중 바이토닉 수열이면서 길이가 가장 긴 것의 길이를 구하라. 부분 수열은 $A$에서 원소를 0개 이상 지우고 남은 원소의 순서를 그대로 둔 수열이다.

첫째 줄에 수열 $A$의 크기 $N$이 주어진다. 둘째 줄에 수열 $A$를 이루는 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le N \le 1000$, $1 \le A_i \le 1000$)

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

첫 번째 예제에서는 1, 2, 3, 4, 5, 2, 1이 가장 긴 바이토닉 부분 수열이고, 길이는 7이다.