HM209 双端月台整队

来源： 第 209 集 deque容器-排序操作

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

双端月台本身没有单独的「排序成员函数」。只要迭代器支持随机访问，就可以把区间交给标准算法 sort：传入 begin() 和 end()，默认按**从小到大**排成升序。使用前必须包含算法头文件。这是标准模板库里的算法组件，不必自己写冒泡或选择排序。

同一组数也可以放进动态数组，再用 sort 排序，结果应与双端月台一致。支持随机访问迭代器的容器都可以这样用。

先按指令把头插、尾插混着装进双端月台（这样通常既不是升序也不是降序），输出排序前的序列；再把**排序前**的同一组数拷进动态数组。分别对双端月台和动态数组调用 sort，再各输出一次，用来确认两种容器都可以排序。

降序写法不属于本题范围。

输入格式

第一行一个整数 \(q\)。

接下来 \(q\) 行，每行两个整数 \(t\)、\(x\)：

• \(t=1\)：push_back(x)
• \(t=2\)：push_front(x)

输出格式

共三行，每行用单个空格分隔，行末无多余空格：

1. 双端月台排序前的序列。
2. 对双端月台 sort 之后的序列。
3. 把月台元素拷入动态数组后再 sort 的序列。

保证最终至少有一个元素。打印月台时使用 const 引用和 const_iterator。

样例

输入 #1

6
1 10
1 20
1 30
2 100
2 200
2 300

输出 #1

300 200 100 10 20 30
10 20 30 100 200 300
10 20 30 100 200 300

输入 #2

4
1 5
1 1
2 4
2 2

输出 #2

2 4 5 1
1 2 4 5
1 2 4 5

说明

\(1 \le q \le 1000\)，\(|x| \le 10^9\)。

sort 的默认规则是升序。支持随机访问迭代器的容器（双端数组、动态数组等）都可以把 [begin, end) 交给它。