题目描述

达达现在碰到了一个棘手的问题，有 $N$ 个整数需要排序。

达达手头能用的工具就是若干个双端队列。

她从 $1$ 到 $N$ 需要依次处理这 $N$ 个数，对于每个数，达达能做以下两件事：

1. 新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2. 将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。

请你求出最少需要多少个双端队列。

输入格式

第一行输入整数 $N$，代表整数的个数。

接下来 $N$ 行，每行包括一个整数 $D_i$，代表所需处理的整数。

输出格式

输出一个整数，代表最少需要的双端队列数。

样例

输入样例：

6
3
6
0
9
6
3

输出样例：

2

样例解释

输入的数依次是：3, 6, 0, 9, 6, 3。

一种最少队列的方案：

• 队列1：依次插入 3（新建），6（尾部），0（头部） → 队列为 [0,3,6]
• 队列2：依次插入 9（新建），6（头部），3（头部） → 队列为 [3,6,9]

最后将两个队列按顺序连接：队列1 + 队列2 → [0,3,6,3,6,9] 排序后不是非降？
等等，要求是“将这些队列按一定的顺序连接起来后就可以得到一个非降的序列”，意思是队列内部已经是按非降顺序（可以是从队头到队尾非降，也可以是从队头到队尾非增，但连接时要能排成非降）。

实际上我们要求的是最小队列数，使得最终连接后整体非降。

更简单的理解：每个队列插入数字后，队列内部是单调的（从队头到队尾非降或非增），并且最终将队列按某种顺序连接起来，整体序列是非降的。
我们要找最小队列数。

在这个例子中，最少需要 2 个队列。

数据范围

• $1 \le N \le 200000$
• $D_i$ 的取值范围未给出，但应该是整数。

时空限制

• 时间限制：1 秒
• 空间限制：64 MB