AT_abc468_f.Chmax

You are given a positive integer $N$ and a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.

There are variables $x,y,c$. Initially, $x=y=c=0$.

For $k=1,2,\ldots,N$ in this order, you perform one of the following operations:

• Operation $1$: Increase $c$ by $1$ if $x < P_k$. Then, replace $x$ with $\max(x,P_k)$.
• Operation $2$: Increase $c$ by $1$ if $y < P_k$. Then, replace $y$ with $\max(y,P_k)$.

Find the maximum possible final value of $c$.

给定一个正整数 $N$ 和 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$。

有三个变量 $x, y, c$，初始时 $x = y = c = 0$。

按 $k = 1, 2, \ldots, N$ 的顺序，对每个 $k$ 执行以下两种操作之一：

• 操作 $1$：若 $x < P_k$，则将 $c$ 增加 $1$；然后将 $x$ 替换为 $\max(x, P_k)$。
• 操作 $2$：若 $y < P_k$，则将 $c$ 增加 $1$；然后将 $y$ 替换为 $\max(y, P_k)$。

求 $c$ 的最终值所能达到的最大可能值。

The input is given from Standard Input in the following format:

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

输入从标准输入中按以下格式给出：

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

Output the answer.

输出答案。

Sample 1 Explanation:
By performing the operations as follows, you can achieve $c=4$:

• For $k=1$: Perform operation $1$. Then, $(x,y,c)=(4,0,1)$.
• For $k=2$: Perform operation $1$. Then, $(x,y,c)=(4,0,1)$.
• For $k=3$: Perform operation $2$. Then, $(x,y,c)=(4,1,2)$.
• For $k=4$: Perform operation $2$. Then, $(x,y,c)=(4,2,3)$.
• For $k=5$: Perform operation $2$. Then, $(x,y,c)=(4,5,4)$.

$c$ cannot be made greater than $4$ no matter how you perform the operations, so output $4$.

Constraints

• $1\le N\le 5\times 10^5$
• $P$ is a permutation of $(1,2,\ldots,N)$.
• All input values are integers.

样例 1 解释：
通过执行如下操作，可使 $c=4$：

• 当 $k=1$ 时：执行操作 1。此时 $(x,y,c)=(4,0,1)$。
• 当 $k=2$ 时：执行操作 1。此时 $(x,y,c)=(4,0,1)$。
• 当 $k=3$ 时：执行操作 2。此时 $(x,y,c)=(4,1,2)$。
• 当 $k=4$ 时：执行操作 2。此时 $(x,y,c)=(4,2,3)$。
• 当 $k=5$ 时：执行操作 2。此时 $(x,y,c)=(4,5,4)$。

无论以何种方式执行操作，$c$ 均无法超过 $4$，因此输出 $4$。

限制条件

• $1\le N\le 5\times 10^5$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列。
• 所有输入值均为整数。