Subsequence Reversal

题目描述

农夫约翰正在将他的 $N$ 头奶牛排成一列拍照（$1 \leq N \leq 50$）。序列中第 $i$ 头奶牛的身高为 $a(i)$，农夫约翰认为，如果这列奶牛按身高有一个很长的递增子序列，那么照片会更加赏心悦目。

回顾一下，子序列是从奶牛序列中取出的一部分元素 $a(i_1), a(i_2), \ldots, a(i_k)$，它们对应的一系列下标满足 $i_1 < i_2 < \ldots < i_k$。如果该子序列满足 $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$，则称其为递增子序列。

FJ 希望在他给奶牛的排列中存在一个很长的递增子序列。为保证这一点，他允许自己一开始可以选择任意一个子序列，并将其中的元素按顺序反转一次。

例如，若我们有序列 1 6 2 3 4 3 5 3 4 我们可以反转选中的元素 1 6 2 3 4 3 5 3 4 ^ ^ ^ ^ 得到 1 4 2 3 4 3 3 5 6 ^ ^ ^ ^ 请注意，被反转的子序列最终仍占据它最初所处的那些下标位置，其他元素保持不变。

请你求出在你可以选择一次任意子序列进行反转的情况下，递增子序列可能达到的最大长度。

输入格式

第一行输入包含 $N$。接下来的 $N$ 行包含 $a(1) \ldots a(N)$，每个都是范围 $1 \ldots 50$ 内的整数。

输出格式

输出在至多反转一个子序列的内容之后，可能形成的最长递增子序列的元素个数。

9
1
2
3
9
5
6
8
7
4

9

提示

题目来源：Lewin Gan

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum