Score : $625$ points

问题陈述

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

• 选择一个介于 $1$ 和 $N$ 之间的整数 $x$，以及任意整数 $y$。将 $A_x$ 替换为 $y$。

执行操作后，找出 $A$ 的最长递增子序列（LIS）的最大可能长度。

什么是最长递增子序列？

序列 $A$ 的一个子序列是通过从 $A$ 中提取一些元素而不改变顺序得到的序列。

序列 $A$ 的一个最长递增子序列是 $A$ 的一个最长子序列，且是严格递增的。

以上为大语言模型 kimi 翻译，仅供参考。

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