双端队列

【题目描述】

有一个初始为空的整数序列 $a=()$。请处理 $Q$ 个查询。

• 0 $x$：将整数 $x$ 添加到序列 $a$ 的开头。
• 1 $x$：将整数 $x$ 添加到序列 $a$ 的末尾。
• 2：删除序列 $a$ 开头的整数。
• 3：删除序列 $a$ 末尾的整数。
• 4 $i$：设此时 $a = (a_0, \ldots, a_{n-1})$。输出 $a_i$。

【输入】

输入格式如下：

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对于每个 4 $i$ 查询，输出一行一个整数，表示 $a_i$。

【输入样例】

11
0 2
1 5
0 3
4 0
4 1
4 2
2
4 0
4 1
3
4 0

【输出样例】

3
2
5
2
5
2

【数据范围】

• $1 \leq Q \leq 500000$
• $0 \leq x \leq 1000000000$
• 执行查询 2、查询 3 或查询 4 时，序列 $a$ 非空。
• 执行查询 4 时，满足 $0\leq i < |a|$。

【来源】

Library Checker（yosupo06） deque