← 返回题目列表

AtCoder · ttpc2015_o

O. 数字顺序着色

中文机器翻译题面 查看原题

問題文

(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