F - Chmax 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

正整数 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 の順に以下の操作のいずれかを行います：

  • 操作 1：x < P_k ならば c を 1 増やす。その後、x を \max(x,P_k) に置き換える。
  • 操作 2：y < P_k ならば c を 1 増やす。その後、y を \max(y,P_k) に置き換える。

最終的な c の値の最大値を求めてください。

制約

  • 1\le N\le 5\times 10^5
  • P は (1,2,\ldots,N) の並び替え
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

5
4 3 1 2 5

出力例 1

4

以下のように操作することで 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 を出力してください。

入力例 2

6
6 5 4 3 2 1

出力例 2

2

入力例 3

9
3 6 5 2 7 8 9 1 4

出力例 3

7

Score : 500 points

Problem Statement

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.

Constraints

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

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.

Sample Input 1

5
4 3 1 2 5

Sample Output 1

4

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.

Sample Input 2

6
6 5 4 3 2 1

Sample Output 2

2

Sample Input 3

9
3 6 5 2 7 8 9 1 4

Sample Output 3

7