← 返回题目列表

Codeforces · 933/A

A. 曲折的运动

中文机器翻译题面 查看原题

龙象征着智慧、力量和财富。大年初一,人们用竹篾和衣服塑龙,用棍举起,高低举竿,形似飞龙。

低举杆的表演者用 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。