P3607 [USACO17JAN] Subsequence Reversal P

题目描述

Farmer John 正在将他的 $N$ 头奶牛排成一列拍照（$1 \leq N \leq 50$）。序列中第 $i$ 头奶牛的高度为 $a(i)$，Farmer John 认为如果奶牛队列中存在一个较长的按高度递增的子序列，那么这张照片会更具美感。

回顾一下，子序列是指从奶牛序列中选出的一组元素 $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$ 到 $50$ 之间的整数。

输出格式

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

输入输出样例 1

9
1
2
3
9
5
6
8
7
4

9