Valeriy 的双端队列

• 时间限制：1.0 s
• 内存限制：512.0 MB

题目描述

最近，在算法与数据结构课程上，Valeriy 学会了如何使用双端队列。他建立了一个包含 $n$ 个元素的双端队列，第 $i$ 个元素为 $a_i$（$i=1,2,\ldots,n$）。他依次从双端队列左侧取出最左边的两个元素（分别称为 $A$ 和 $B$），然后进行如下操作：如果 $A > B$，则将 $A$ 放回队列最前面，将 $B$ 放到队列最后面；否则，将 $B$ 放到队列最前面，将 $A$ 放到队列最后面。我们称这一系列动作为一次操作。

例如，如果双端队列为 $[2, 3, 4, 5, 1]$，在一次操作中，他会将 $B=3$ 放到队列最前面，将 $A=2$ 放到队列最后面，得到 $[3, 4, 5, 1, 2]$。

课程老师看到 Valeriy 如此投入，便给了他 $q$ 个询问。每个询问包含一个正整数 $m_j$（$j=1,2,\ldots,q$）。对于每个询问，需要回答在第 $m_j$ 次操作时，他会取出的那两个元素分别是什么。

注意，所有询问相互独立，对于每个询问，都应输出按照取出顺序的 $A$ 和 $B$。

双端队列是一种数据结构，支持从两端插入和删除元素。

输入格式

第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 10^5$，$0 \leq q \leq 3 \times 10^5$）——双端队列中的元素个数和询问个数。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，其中 $a_i$（$0 \leq a_i \leq 10^9$）表示第 $i$ 个位置的元素。接下来的 $q$ 行，每行包含一个整数 $m_j$（$1 \leq m_j \leq 10^{18}$）。

输出格式

对于每个老师的询问，输出两个整数 $A$ 和 $B$，表示在第 $m_j$ 次操作时，Valeriy 取出的那两个元素，按照取出顺序输出。

输入输出样例

输入样例 #1

5 3
1 2 3 4 5
1
2
10

输出样例 #1

1 2
2 3
5 2

输入样例 #2

2 0
0 0

输出样例 #2

说明/提示

以第一个测试样例为例，详细考虑前 10 步操作：

1. $[1, 2, 3, 4, 5]$ —— 第一次操作，$A=1$，$B=2$，将 $2$ 放到队首，$1$ 放到队尾。
2. 得到队列状态 $[2, 3, 4, 5, 1]$。
3. $[2, 3, 4, 5, 1] \Rightarrow A=2, B=3$。
4. $[3, 4, 5, 1, 2]$。
5. $[4, 5, 1, 2, 3]$。
6. $[5, 1, 2, 3, 4]$。
7. $[5, 2, 3, 4, 1]$。
8. $[5, 3, 4, 1, 2]$。
9. $[5, 4, 1, 2, 3]$。
10. $[5, 1, 2, 3, 4]$。
11. $[5, 2, 3, 4, 1] \Rightarrow A=5, B=2$。

数据范围

• $2 \le n \le 10^5$
• $0 \le q \le 3 \times 10^5$
• $0 \le a_i \le 10^9$
• $1 \le m_j \le 10^{18}$

提示

队列中的最大值一旦到达队首，就会永远留在队首，此后每次操作只会取出该最大值与队首之后的第一个元素，并使其在剩余的 $n-1$ 个元素中循环。因此只需模拟到最大值到达队首（至多 $n-1$ 次操作），剩下的询问用周期公式 $O(1)$ 回答。

时间复杂度 $O(n + q)$，空间复杂度 $O(n)$。