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)$ 的一个排列。