CF1179A Valeriy and Deque

最近，在算法与数据结构课程上，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 取出的那两个元素，按照取出顺序输出。

以第一个测试样例为例，详细考虑前 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$。 由 ChatGPT 4.1 翻译