大样例下载

题目描述

给出一个序列 A[1..n]

你可以任选 A 的一个子序列将其翻转，其它非所选子序列的元素位置不变。

你最多只能翻转一次。

问：你可以得到的最长不下降子序列的长度是多少？

输入格式

第一行：一个整数 n

第二行：n 个整数 A1, A2, ……, An

输出格式

一个整数，表示答案

输入样例1

9
1 6 2 3 4 3 5 3 4

输出样例1

7

样例解释 1

方案可能不唯一，一种可能的方案是：

1 6 2 3 4 3 5 3 4

===>

1 4 2 3 3 4 5 3 6

输入样例2

9
1 2 3 9 5 6 8 7 4

输出样例2

9

样例解释 2

1 2 3 9 5 6 8 7 4

===>

1 2 3 4 5 6 7 8 9

数据范围

100% 的数据：1 ≤ n, Ai ≤ 50