← 返回题目列表

Codeforces · 1179/A

A. 瓦列里和德克

中文机器翻译题面 查看原题

最近,在算法和数据结构的课程中,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 \cdot 10^5$$$) - 双端队列中的元素数量和查询数量。第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$,其中 $$$a_i$$$ $$$(0 \leq a_i \leq 10^9)$$$ — 第 $$$i$$$ 个位置的双端队列元素。接下来的 $$$q$$$ 行每行包含一个数字,表示 $$$m_j$$$ ($$$1 \leq m_j \leq 10^{18}$$$)。

输出

对于每位教师的查询,输出两个数字 $$$A$$$ 和 $$$B$$$ — Valeriy 从第 $$$m_j$$$ 操作的双端队列中取出的数字。

示例

输入 #1

5 3
1 2 3 4 5
1
2
10

输出 #1

1 2
2 3
5 2

输入 #2

2 0
0 0

输出 #2

注意

1. $$$[1, 2, 3, 4, 5]$$$ — 在第一个操作中,$$$A$$$ 和 $$$B$$$ 分别是 $$$1$$$ 和 $$$2$$$。因此,$$$2$$$ 写入双端队列的开头,$$$1$$$ — 写入双端队列的末尾。我们得到以下状态双端队列:$$$[2,3,4,5,1]$$$。
2. $$$[2, 3, 4, 5, 1] \右箭头 A = 2,B = 3$$$。
3. $$$[3, 4, 5, 1, 2]$$$
4. $$$[4, 5, 1, 2, 3]$$$
5. $$$[5, 1, 2, 3, 4]$$$
6. $$$[5, 2, 3, 4, 1]$$$
7. $$$[5, 3, 4, 1, 2]$$$
8. $$$[5, 4, 1, 2, 3]$$$
9. $$$[5, 1, 2, 3, 4]$$$
10. $$$[5, 2, 3, 4, 1] \右箭头 A = 5,B = 2$$$。