Source : 长沙雅礼中学
Description

大动物联邦之主为了扫四合,决定给你一个长度为n的序列\{ {a}_{i} \}

由于九彩神母鹿曾经是个卧底,常常反向打自己人,所以现在你可以选择任意一个区间[l,r]并将区间内的数逆序。

万兽之王已经扫了三合,现在要爬山去攻打勇国,于是她问操作之后序列\{ {a}_{i} \}的最长不下降子序列长度。

区间只能被翻转一次。

Input

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

然后一行共n个整数{a}_{i}

Output

一行一个整数ans表示最长不下降子序列的长度。

Sample Input 1
4
1 2 1 2
Sample Output 1
4
Sample Input 2
10
1 1 2 2 2 1 1 2 2 1
Sample Output 2
9
Sample Input 3
45
1 1 2 2 1 1 2 1 2 1 1 2 2 2 2 1 2 1 2 1 1 2 1 1 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 2 2 1 2 1 1
Sample Output 3
31
Hint

样例1解释:

考虑将2->3翻转,那么整个序列就变成 1,1,2,2,显然整个序列都是不下降的。

数据范围:

对于所有数据{a}_{i}\in \{ 1,2\}

对于前10%的数据,满足{a}_{i} = 1

对于前30%的数据,满足n<=50。

对于前70%的数据,满足n<=2000。

对于前100%的数据,满足n<=106