题目描述

题目译自 CEOI 2022 Day1 T1「Abracadabra」

Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。

Tin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。

事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 $n$ 张牌的顺序，接着采用如下技巧洗牌：

1. 拿起自顶向下 $\frac{n}{2}$ 张牌放在右手，自底向上 $\frac{n}{2}$ 张牌放在左手，牌的正面对着桌子。
2. 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。
3. 将还有牌的那只手上的所有牌放下。

请你写一个程序模拟 Tin 的魔术。

输入格式

第一行两个整数 $N,Q$。

接下来一行 $N$ 个整数 $p_i$，从底向上描述了整个牌堆。

接下来 $Q$ 行，一行一个询问 $t,i$，表示询问 $t$ 次洗牌后自底向上第 $i$ 张牌编号是多少。

输出格式

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

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

数据范围与提示

对于全部数据，满足 $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$。