뒤틀린 움직임

용은 지혜, 힘, 부를 상징한다. 음력 설날에 사람들은 대나무 조각과 천으로 용 모형을 만들고, 막대로 이를 들어 올린 뒤 막대를 높고 낮게 움직여 날아가는 용의 모습을 표현한다.

막대를 낮게 들고 있는 공연자는 1로, 높게 들고 있는 공연자는 2로 나타낸다. 따라서 공연자들의 줄은 수열 a1, a2, ..., an으로 나타낼 수 있다.

Little Tommy도 그들 중 한 명이다. 그는 구간 [l, r] (1 ≤ l ≤ r ≤ n)을 선택한 다음 al, al + 1, ..., ar을 뒤집어, 새로운 수열의 최장 비감소 부분 수열 길이를 최대로 만들고자 한다.

비감소 부분 수열은 p1 < p2 < ... < pk이고 ap1 ≤ ap2 ≤ ... ≤ apk인 인덱스의 수열 p1, p2, ..., pk이다. 이 부분 수열의 길이는 k이다.

첫 번째 줄에 원래 수열의 길이를 나타내는 정수 n (1 ≤ n ≤ 2000)이 주어진다.

두 번째 줄에 원래 수열 a1, a2, ..., an을 나타내는 공백으로 구분된 n개의 정수 (1 ≤ ai ≤ 2, i = 1, 2, ..., n)이 주어진다.

새로운 수열에서 가능한 최장 비감소 부분 수열 길이의 최댓값을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 $[2, 3]$을 뒤집으면 배열은 $[1, 1, 2, 2]$이 되며, 이 배열의 최장 비감소 부분 수열 길이는 4이다.

두 번째 예제에서 $[3, 7]$을 뒤집으면 배열은 $[1, 1, 1, 1, 2, 2, 2, 2, 2, 1]$이 되며, 이 배열의 최장 비감소 부분 수열 길이는 9이다.