P8996 [CEOI 2022] Abracadabra

Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。 Tin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。 事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 $n$ 张牌的顺序，接着采用如下技巧洗牌： 1. 拿起自顶向下 $\frac{n}{2}$ 张牌放在右手，自底向上 $\frac{n}{2}$ 张牌放在左手，牌的正面对着桌子。 1. 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。 1. 将还有牌的那只手上的所有牌放下。 请你写一个程序模拟 Tin 的魔术。

第一行两个整数 $N,Q$。 接下来一行 $N$ 个整数 $p_i$，从底向上描述了整个牌堆。 接下来 $Q$ 行，一行一个询问 $t,i$，表示询问 $t$ 次洗牌后自底向上第 $i$ 张牌编号是多少。

对于每一个询问，输出你的答案。

### 样例 3 解释 | 洗牌次数 | 自底向上的牌堆 | | :------: | :-----------------------------: | | $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$ | ### 数据规模与约定 对于全部数据，满足 $1\le N\le 2\times 10^5$，$N$ 为偶数，$1\le Q\le 10^6$，$0\le t\le 10^9$，$p$ 为 $1\sim n$ 的排列，$1\le i\le N$。 | Subtask 编号 | 特殊限制 | 分数 | | :----------: | :------------------: | :------: | | $1$ | $N\le 10^3$ | $10$ | | $2$ | 每一个询问的 $t$ 相同 | $40$ | | $3$ | $N,Q\le 10^5$ | $25$ | | $4$ | 无特殊限制 | $25$ |