题目描述

给你一个长度为 N 的整数序列 A。小Y将恰好执行以下操作一次：

选择一个在 1 到 N（包括）之间的整数 i，以及一个任意整数 y。将 $A_i$ 替换为 y。 找到执行操作后 A 的最长递增子序列 (LIS) 的最大可能长度。

输入格式

输入从标准输入给出，格式如下： N A_1 A_2 ... A_N

输出格式

在一行中打印答案。

4
3 2 2 4

3

给定序列的 LIS 的长度是 2。例如，如果你将 A_1 替换为 1，LIS 的长度变为 3，这是最大值。

5
4 5 3 6 7

4

给定序列的 LIS 的长度是 4。

约束

$1 \le N \le 2\times 10^5$
$1 \le A_i \le 10^9$