P8996 [CEOI 2022] Abracadabra

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. 1. 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. 1. Put down all remaining cards in the non-empty hand. Please write a program to simulate Tin’s trick.

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.

For each query, output the answer.

### Explanation for Sample 3 | Number of shuffles | Deck from bottom to top | | :----------------: | :---------------------------------------------: | | $0$ | $7\ 5\ 2\ 9\ 10\ 8\ 4\ 3\ 6\ 1$ | | $1$ | $7\ 5\ 2\ 8\ 4\ 3\ 6\ 1\ 9\ 10$ | | $2$ | $3\ 6\ 1\ 7\ 5\ 2\ 8\ 4\ 9\ 10$ | | $3$ | $2\ 3\ 6\ 1\ 7\ 5\ 8\ 4\ 9\ 10$ | ### 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$. | Subtask ID | Special constraints | Score | | :--------: | :---------------------------------: | :---: | | $1$ | $N \le 10^3$ | $10$ | | $2$ | All queries have the same $t$ | $40$ | | $3$ | $N, Q \le 10^5$ | $25$ | | $4$ | No special constraints | $25$ | Translated by ChatGPT 5