Description

【题目描述】

小 A 有一个长度为 $n$ 的序列 $a$，满足 $a$ 中的所有元素都是 $1$ 或 $2$。

你想要篡改这个序列。你可以任意选择原序列的一段区间 $[l,r]$，并将 $a_l, a_{l+1},\cdots, a_r$ 翻转。为了不被发现，你只能执行该操作至多一次。

你希望最大化操作之后序列最长不下降子序列的长度，请求出这个值。

序列 $a$ 的一个不下降子序列是一个下标序列 $p_1, p_2,\cdots, p_k$，满足 $p_1 < p_2 <\cdots < p_k$ 且 $a_{p_1} \le a_{p_2} \le \cdots \le a_{p_k}$ 。定义它的长度为 $k$。

Input Format

【输入格式】

从文件 $sanrd.in$ 中读入数据。

第一行一个整数 $n$，表示序列的长度。

第二行 $n$ 个用空格隔开的正整数，描述了序列 $a$。

Output Format

【输出格式】

输出到文件 $sanrd.out$ 中。

输出一行一个整数，表示操作之后序列最长不下降子序列长度的最大值。

Sample

【样例 1 输入】

4
1 2 1 2

【样例 1 输出】

4

【样例 2 输入】

10
1 1 2 2 2 1 1 2 2 1

【样例 2 输出】

9

Hint

【样例 2 解释】

你可以选择区间 $[3, 7]$ 并将其翻转，得到的序列为 $[1, 1, 1, 1, 2, 2, 2, 2, 2, 1]$，它的最长不下降子序列的长度为 $9$。不难发现对于这组数据不存在更优的解。

【子任务】

对于 $60\%$ 的数据，$n \le 200$；

对于 $90\%$ 的数据，$n \le 2000$；

对于 $100\%$ 的数据，$1 \le n \le 2\times 10^5, 1 \le a_i \le 2$。