10112 가장 긴 바이토닉 부분수열 Gold IV

문제

수열 S가 주어졌을 때, 가장 긴 바이토닉 부분수열의 길이를 구하시오.

바이토닉 부분수열이란 S_1 < … < S_k > … > S_N인 수열이다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에 수열이 주어진다.

출력

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

10
1 5 2 1 4 3 4 5 2 1

7