103606: [Atcoder]ABC360 G - Suitable Edit for LIS

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

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

得分:625分

问题陈述

给你一个长度为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

加入题单

上一题 下一题 算法标签: