A Twisty Movement

용은 지혜, 힘, 부를 상징한다. On Lunar New Year's Day, 사람들은 대나무 조각과 천으로 용의 형상을 만들고, 막대로 이를 들어 올리며, 날아가는 용처럼 보이도록 막대를 높고 낮게 든다.

막대를 낮게 든 공연자는 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 (1 ≤ ai ≤ 2, i = 1, 2, ..., n)을 나타내는 공백으로 구분된 정수 n개가 주어진다.

새로운 수열의 최장 비감소 부분 수열이 가질 수 있는 최대 길이를 나타내는 하나의 정수를 출력한다.

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

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