单点修改后的最长上升子序列

题目描述

给定长度为 $N$ 的整数序列 $A$。高桥将进行以下操作恰好一次:

选择满足 $1 \le x \le N$ 的整数 $x$ 和任意整数 $y$,将 $A_x$ 替换为 $y$。

求操作后 $A$ 的最长上升子序列(LIS)长度的最大值。

什么是最长上升子序列?

序列 $A$ 的子序列是指从 $A$ 中按原顺序取出部分元素得到的序列。

序列 $A$ 的最长上升子序列是指 $A$ 的最长的严格递增的子序列。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

在一行内输出答案。

样例

4
3 2 2 4

3

给定序列 $A$ 的 LIS 长度为 2。例如,将 $A_1$ 替换为 1 后,$A$ 的 LIS 长度变为 3,这是最大值。

5
4 5 3 6 7

4

数据范围

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