AT_ttpc2015_o 数列色ぬり

给定一个 $(1,2,\cdots,N)$ 的排列 $a_1,a_2,\cdots,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$。 第二行 $N$ 个整数，第 $i$ 个整数表示 $a_i$。

输出仅一行，涂色元素数量的最大值。

### 样例解释 #1 一种涂色方案是：将 $ a_1 $、$ a_4 $ 涂成红色，$ a_2 $、$ a_3 $ 涂成蓝色。 ### 样例解释 #2 所有元素都可以涂成红色。 ### 样例解释 #3 可以将 $a_2$、$a_3$ 涂成红色，$a_1$、$a_4$ 涂成蓝色。 ### 数据范围 + $1 \leq N \leq 10^5$ + 保证 $a_1,a_2,\cdots,a_N$ 是 $(1,2,\cdots,N)$ 的一个排列。