AT_ttpc2015_o 数列色ぬり

[problemUrl]: https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_o $ (1,\ 2,\ …,\ N) $ の順列として数列 $ a_1,\ a_2,\ …,\ a_N $ が与えられます。 あなたは、この数列のうちいくつかの要素を、以下の条件を満たすように赤色または青色に塗ることができます。 - すべての $ i,\ j(1\ \leq\ i\

入力は以下の形式で標準入力から与えられる。 > $ 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) $ の順列である。

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

### Sample Explanation 1 塗り方の一例として、$ a_1,\ a_4 $ を赤色に塗り $ a_2,\ a_3 $ を青色に塗るという方法があります。 ### Sample Explanation 2 すべての要素を赤色に塗ることができます ### Sample Explanation 3 $ a_2,\ a_3 $ を赤色に塗り $ a_1,\ a_4 $ を青色に塗ればよいです