bzoj#P2457. [BeiJing2011] 双端队列
[BeiJing2011] 双端队列
题目描述
Sherry 现在碰到了一个棘手的问题,她需要对 个整数排序。
Sherry 手头能用的工具就是若干个双端队列。
她需要依次处理这 个数,对于每个数,Sherry 能做以下两件事:
- 新建一个双端队列,并将当前数作为这个队列中的唯一的数。
- 将当前数放入已有的队列的头之前或者尾之后。 对所有的数处理完成之后,Sherry 将这些队列排序后就可以得到一个非降的序列。
输入格式
第一行包含一个整数 ,表示整数的个数。
接下来的 行每行包含一个整数 ,其中 表示所需处理的整数。
输出格式
其中只包含一行,为 Sherry 最少需要的双端队列数。
6
3
6
0
9
6
3
2
数据范围与提示