O - 数列色ぬり Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

(1,\ 2,\ …,\ N) の順列として数列 a_1,\ a_2,\ …,\ a_N が与えられます。

あなたは、この数列のうちいくつかの要素を、以下の条件を満たすように赤色または青色に塗ることができます。

  • すべての i,\ j(1 \leq i < j \leq N) について、a_i,\ a_j がともに赤色に塗られているならば a_i < a_j
  • すべての i,\ j(1 \leq i < j \leq N) について、a_i,\ a_j がともに青色に塗られているならば a_i > a_j

あなたは色を塗る要素を出来る限り多くしたいです。

色を塗る要素の個数の最大値を求めてください。

入力

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

N
a_1 a_2 … a_N
  • 1 行目には整数 N(1 \leq N \leq 10^5) が与えられる。
  • 2 行目には数列 a_i が空白区切りで与えられる。
  • a_1,\ a_2,\ ,…,\ a_N は (1,\ 2,\ …,\ N) の順列である。

出力

色を塗る要素の個数の最大値を一行に出力せよ。出力は標準出力に行い、末尾には改行を入れること。

入力例1

5
3 4 1 5 2

出力例1

4

塗り方の一例として、a_1, a_4 を赤色に塗り a_2, a_3 を青色に塗るという方法があります。

入力例2

7
1 2 3 4 5 6 7

出力例1

7

すべての要素を赤色に塗ることができます

入力例3

4
3 1 4 2

出力例3

4

a_2, a_3 を赤色に塗り a_1, a_4 を青色に塗ればよいです

入力例3

20
18 13 16 20 10 8 15 2 11 19 3 5 1 4 9 7 14 12 17 6

出力例3

12