問題文
(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