103606: [Atcoder]ABC360 G - Suitable Edit for LIS
Description
Score : $625$ points
Problem Statement
You are given an integer sequence $A$ of length $N$. Takahashi will perform the following operation exactly once:
- Choose an integer $x$ between $1$ and $N$, inclusive, and an arbitrary integer $y$. Replace $A_x$ with $y$.
Find the maximum possible length of a longest increasing subsequence (LIS) of $A$ after performing the operation.
What is longest increasing subsequence?
A subsequence of a sequence $A$ is a sequence that can be derived from $A$ by extracting some elements without changing the order.
A longest increasing subsequence of a sequence $A$ is a longest subsequence of $A$ that is strictly increasing.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
Print the answer on a single line.
Sample Input 1
4 3 2 2 4
Sample Output 1
3
The length of a LIS of the given sequence $A$ is $2$. For example, if you replace $A_1$ with $1$, the length of a LIS of $A$ becomes $3$, which is the maximum.
Sample Input 2
5 4 5 3 6 7
Sample Output 2
4
Output
问题陈述
给你一个长度为N的整数序列A。高桥将执行以下操作恰好一次：
- 在1和N之间（包括1和N）选择一个整数x和一个任意的整数y。用y替换Ax。
找出执行操作后A的最长递增子序列（LIS）的最大可能长度。
什么是最长递增子序列？
序列A的子序列是从A中提取一些元素而不改变顺序得到的序列。
序列A的最长递增子序列是A的最长严格递增的子序列。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
输入
输入从标准输入以以下格式给出：
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
输出
在一行内打印答案。
示例输入1
4 3 2 2 4
示例输出1
3
给定序列A的LIS长度为2。例如，如果你用1替换A1，A的LIS长度变为3，这是最大的。
示例输入2
5 4 5 3 6 7
示例输出2
4