1006: 子序列2
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
给出一个由$n$个整数组成的序列，你可以在原序列中任意插入一个数，求修改后序列中由连续自然数组成的最长上升子序列。
注意是“由连续自然数组成的”，以原序列为$[6,2,6,3,5,4,9]$为例，其符合本题要求的最长子序列为$[2,3,4]$，而非通常认为的$[2,3,4,9]$。
输入
第一行，一个整数$n$。
第二行，$n$个整数，表示初始序列各元素值$A_i$。
输出
一个整数，表示修改后序列中由连续自然数组成的最长上升子序列的长度。
样例输入 复制
#1
4
1 1 2 2
#2
5
2 3 1 3 5
#3
6
2 1 2 3 5 7样例输出 复制
#1
3
#2
4
#3
5提示
【样例解释】
对于样例1：
插入$3$后序列变为$[1,1,2,2,3]$，其中由连续自然数组成的最长上升子序列为$[1,2,3]$
对于样例2： 插入$4$后序列变为$[2,3,1,4,3,5]$，其中由连续自然数组成的最长上升子序列为$[2,3,4,5]$
对于样例3： 插入$4$后序列变为$[2,1,2,3,4,5,7]$，其中由连续自然数组成的最长上升子序列为$[1,2,3,4,5]$
【数据范围】
对于20%的数据：
$1 \leq n,A_i \leq 20$
对于100%的数据：
$1 \leq n,A_i \leq 10^6$