Suitable Edit for LIS

题目描述

给定长度为 $N$ 的整数序列 $A$ 。Takahashi 将恰好执行一次以下操作：

选择一个整数 $x$ ，满足 $1 \le x \le N$ ，以及任意整数 $y$ 。用 $y$ 替换 $A_x$ 。

在执行该操作之后，求序列 $A$ 的最长严格递增子序列（LIS）长度的最大可能值。

什么是最长严格递增子序列？

序列 $A$ 的一个子序列是可以通过从 $A$ 中按原顺序抽取若干元素得到的序列。

序列 $A$ 的一个最长严格递增子序列是 $A$ 的所有严格递增子序列中长度最长的一个。

输入从标准输入按以下格式给出： $N$ $A_1$ $A_2$ $\cdots$ $A_N$

在一行中输出答案。

4
3 2 2 4

5
4 5 3 6 7

$1 \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq 10^9$ 给定序列 $A$ 的一个 LIS 的长度为 $2$ 。例如，如果将 $A_1$ 替换为 $1$ ，则 $A$ 的 LIS 长度变为 $3$ ，这是最大可能值。

标签: AtCoder|abc360G

AtCoder|abc360G