/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
長さ N の整数列 A が与えられます。高橋くんは、 1 回だけ次の操作をします。
- 1 以上 N 以下の整数 x と、任意の整数 y を選ぶ。A_x を y に置き換える。
操作をした後の A の最長増加部分列の長さとしてあり得る最大の値を求めてください。
最長増加部分列とは？
列 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 行に出力せよ。
入力例 1
4 3 2 2 4
出力例 1
3
与えられた数列 A の LIS の長さは 2 です。例えば A_1 を 1 に置き換えると、操作後の A の LIS の長さが 3 になり、これが最大です。
入力例 2
5 4 5 3 6 7
出力例 2
4
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