[BeiJing2011]双端队列

Sherry 遇到了一个棘手的问题：她需要将 $N$ 个整数排序，而手头能使用的工具只有若干个双端队列。

她必须按照输入顺序依次处理这 $N$ 个整数。对于当前处理的整数，Sherry 可以执行以下两种操作之一：

• 新建一个双端队列，并将当前整数作为该队列中唯一的元素；
• 将当前整数插入某个已有双端队列的队首之前或队尾之后。

处理完所有整数后，Sherry 可以任意调整这些双端队列之间的顺序，但不能改变任何一个双端队列内部元素的顺序。随后，她按照调整后的队列顺序，依次从每个队列的队首到队尾读出全部元素，并将结果连接成一个序列。

Sherry 要求最终得到的序列为非降序列。请计算她最少需要建立多少个双端队列。

输入格式

第一行包含一个整数 $N$，表示需要处理的整数个数。

接下来的 $N$ 行，每行包含一个整数 $D_i$，表示第 $i$ 个需要处理的整数。

输出格式

输出一行，包含一个整数，表示 Sherry 最少需要建立的双端队列数量。

样例输入

6
3
6
0
9
6
3

样例输出

2

数据范围

• 对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$；
• $-2^{31}\le D_i\le 2^{31}-1$。

来源与许可

本题为 Beijing 2011 试题「双端队列」，题面与测试数据整理自 BZOJ。

样例 1

输入

6
3
6
0
9
6
3

输出

2