Problem Description

Tin is a famous magician. One of his classic tricks is about shuffling cards.

Tin prepares a deck of cards with a total of $n$ cards (it is guaranteed that $n$ is even), numbered $1 \sim n$. At the beginning, the deck is in a random order and placed face down on the table. Then he starts performing the shuffle. At any moment during the shuffle, the audience may ask Tin which card is the $t$-th card from the bottom. Obviously, Tin can always immediately give the correct answer.

In fact, Tin performs the trick as follows. First, he memorizes the initial order of the $n$ cards, and then shuffles using this technique:

1. Pick up the top $\frac{n}{2}$ cards with his right hand, and the bottom $\frac{n}{2}$ cards with his left hand, with the faces of the cards towards the table.
2. Using his memory, compare the bottom cards of the left and right hands. Put down the card with the smaller number. Repeat this operation until one hand becomes empty.
3. Put down all remaining cards in the non-empty hand.

Please write a program to simulate Tin’s trick.

Input Format

The first line contains two integers $N, Q$.

The next line contains $N$ integers $p_i$, describing the whole deck from bottom to top.

The next $Q$ lines each contain one query $t, i$, meaning: after $t$ shuffles, what is the card number of the $i$-th card from the bottom.

Output Format

For each query, output the answer.

6 3
1 5 6 2 3 4
1 2
0 4
1 5

2
2
5

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6

2
2
5
4
3
3

10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10

2
3
6
1
7
5
8
4
9
10

Hint

Explanation for Sample 3

Constraints

For all testdata, $1 \le N \le 2 \times 10^5$, $N$ is even, $1 \le Q \le 10^6$, $0 \le t \le 10^9$, $p$ is a permutation of $1 \sim n$, and $1 \le i \le N$.

Translated by ChatGPT 5