0x10基本数据结构（0x12 队列）例题3：双端队列[BJOI2011]

【题意】

有 $n$ 个整数 $a_i$ 需要排序。

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

依次处理这 $n$ 个数，对于每个数，能做以下两件事：

• 1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

• 2．将当前数放入已有的队列的头之前或者尾之后。

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

求最少需要多少个双端序列。

【输入格式】

第一行一个整数 $n \ (1 ≤ n ≤ 200000)$。

下来 $n$ 个整数 $a_i$ 。

【输出格式】

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

【输入样例】

6
3 6 0 9 6 3

【输出样例】

2