Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:512 MB

#2024. Abracadabra

Statistics

题目描述

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$ 张牌编号是多少。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2
2
5

样例 #2

样例输入 #2

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

样例输出 #2

2
2
5
4
3
3

样例 #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

样例输出 #3

2
3
6
1
7
5
8
4
9
10

提示

样例 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$