龙象征着智慧、力量和财富。大年初一,人们用竹篾和衣服塑龙,用棍举起,高低举竿,形似飞龙。
低举杆的表演者用 1 表示,高举杆的表演者用 2 表示。因此,表演者的队伍可以用序列 a1, a2, ..., an 表示。
小汤米就是其中之一。他想选择一个区间[l,r](1≤l≤r≤n),然后将al,al+1,…,ar反转,使得新序列的最长非减子序列的长度最大。
非递减子序列是索引 p1, p2, ..., pk 的序列,使得 p1 < p2 < ... < pk 且 ap1 ≤ ap2 ≤ ... ≤ apk。子序列的长度为k。
输入
第一行包含一个整数n(1≤n≤2000),表示原始序列的长度。
第二行包含 n 个空格分隔的整数,描述原始序列 a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n)。
输出
打印单个整数,表示新序列的最长非递减子序列的最大可能长度。
示例
输入 #1
4 1 2 1 2
输出 #1
4
输入 #2
10 1 1 2 2 2 1 1 2 2 1
输出 #2
9
注意
在第一个示例中,将 [2, 3] 反转后,数组将变为 [1, 1, 2, 2],其中最长非递减子序列的长度为 4。
在第二个例子中,将[3, 7]反转后,数组将变为[1, 1, 1, 1, 2, 2, 2, 2, 2, 1],其中最长非递减子序列的长度为9。