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