[ABC360] G - Suitable Edit for LIS

G - Suitable Edit for LIS

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：625 分

题面

给定一个长度为 的整数序列 。高桥将执行以下操作一次：

• 选择一个介于 到 之间的整数 ，以及任意整数 。将 替换为 。

在执行操作后，找出 的最长递增子序列（LIS）的最大可能长度。

什么是最长递增子序列？

序列 的一个子序列是指可以通过提取 中的一些元素而不改变其顺序而得到的序列。

序列 的一个最长递增子序列是指严格递增的 的最长子序列。

限制条件

---

输入

输入从标准输入中以以下格式给出：

输出

在一行上输出答案。

---

输入样例 1

4
3 2 2 4

输出样例 1

3

给定序列 的 LIS 长度为 。例如，如果你将 替换为 ，则 的 LIS 长度变为 ，这是最大的。

---

输入样例 2

5
4 5 3 6 7

输出样例 2

4