Valeriy and Deque

题意翻译

给定一个双端队列，然后给定一个$operation$，每一个$operation$可以实现以下步骤： 1. 取出队列的前两个元素，分别是$A$，$B$。 2. 如果$A>B$，那么$A$加入到这个队列的$front$，$B$加入到$back$，否则$A$加入$back$，B加入$front$。，然后给你q个询问，每一个询问是问你从原始数组开始执行第$x$次$operation$时，$A$和$B$分别是多少？ 整理by破壁人四号 来自https://www.cnblogs.com/qieqiemin/p/11070137.html

题目描述

Recently, on the course of algorithms and data structures, Valeriy learned how to use a deque. He built a deque filled with $ n $ elements. The $ i $ -th element is $ a_i $ ( $ i $ = $ 1, 2, \ldots, n $ ). He gradually takes the first two leftmost elements from the deque (let's call them $ A $ and $ B $ , respectively), and then does the following: if $ A > B $ , he writes $ A $ to the beginning and writes $ B $ to the end of the deque, otherwise, he writes to the beginning $ B $ , and $ A $ writes to the end of the deque. We call this sequence of actions an operation. For example, if deque was $ [2, 3, 4, 5, 1] $ , on the operation he will write $ B=3 $ to the beginning and $ A=2 $ to the end, so he will get $ [3, 4, 5, 1, 2] $ . The teacher of the course, seeing Valeriy, who was passionate about his work, approached him and gave him $ q $ queries. Each query consists of the singular number $ m_j $ $ (j = 1, 2, \ldots, q) $ . It is required for each query to answer which two elements he will pull out on the $ m_j $ -th operation. Note that the queries are independent and for each query the numbers $ A $ and $ B $ should be printed in the order in which they will be pulled out of the deque. Deque is a data structure representing a list of elements where insertion of new elements or deletion of existing elements can be made from both sides.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 2 \leq n \leq 10^5 $ , $ 0 \leq q \leq 3 \cdot 10^5 $ ) — the number of elements in the deque and the number of queries. The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ , where $ a_i $ $ (0 \leq a_i \leq 10^9) $ — the deque element in $ i $ -th position. The next $ q $ lines contain one number each, meaning $ m_j $ ( $ 1 \leq m_j \leq 10^{18} $ ).

输出格式

For each teacher's query, output two numbers $ A $ and $ B $ — the numbers that Valeriy pulls out of the deque for the $ m_j $ -th operation.

输入输出样例

输入样例 #1

5 3
1 2 3 4 5
1
2
10

输出样例 #1

1 2
2 3
5 2

输入样例 #2

2 0
0 0

输出样例 #2

说明

Consider all 10 steps for the first test in detail:2. $ [1, 2, 3, 4, 5] $ — on the first operation, $ A $ and $ B $ are $ 1 $ and $ 2 $ , respectively.So, $ 2 $ we write to the beginning of the deque, and $ 1 $ — to the end. We get the following status of the deque: $ [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 $ .