1179A.md (2711B)
1 Source: https://codeforces.com/problemset/problem/1179/A 2 3 A. Valeriy and Deque 4 5 time limit per test 6 7 6 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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 \gt 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. 22 23 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]$. 24 25 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. 26 27 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. 28 29 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. 30 31 Input 32 33 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}$). 34 35 Output 36 37 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. 38 39 Examples 40 41 Input 42 43 ``` 44 5 3 45 1 2 3 4 5 46 1 47 2 48 10 49 ``` 50 51 Output 52 53 ``` 54 1 2 55 2 3 56 5 2 57 ``` 58 59 Input 60 61 ``` 62 2 0 63 0 0 64 ``` 65 66 Output 67 68 Note 69 70 Consider all 10 steps for the first test in detail:1. $[1, 2, 3, 4, 5]$ — on the first operation, $A$ and $B$ are $1$ and $2$, respectively. 71 72 So, $2$ we write to the beginning of the deque, and $1$ — to the end. 73 74 We get the following status of the deque: $[2, 3, 4, 5, 1]$. 75 2. $[2, 3, 4, 5, 1] \Rightarrow A = 2, B = 3$. 76 3. $[3, 4, 5, 1, 2]$ 77 4. $[4, 5, 1, 2, 3]$ 78 5. $[5, 1, 2, 3, 4]$ 79 6. $[5, 2, 3, 4, 1]$ 80 7. $[5, 3, 4, 1, 2]$ 81 8. $[5, 4, 1, 2, 3]$ 82 9. $[5, 1, 2, 3, 4]$ 83 10. $[5, 2, 3, 4, 1] \Rightarrow A = 5, B = 2$.