对称旅行者

题目信息

时间限制: 1s

空间限制: 512M

输入文件: bubble.in

输出文件: bubble.out

题目描述

冒泡演出是 CS 大学的军训结束表演，由 $n$ 位同学组成，每位同学都领取一个从 $1$ 到 $n$ 的编号，同学们的编号两两不同。

冒泡演出的内容很简单，刚开始 $n$ 位同学站成一排，同学们的编号形成一个排列 $a[1\dots n]$，教官每吹一次哨，同学们就进行一次冒泡排序：

for (int i = 1; i < n; i++) {
    if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);
}

众所周知，教官至多吹 $n - 1$ 次哨后，同学们手中的编号恰好就会形成升序排列 $1, 2, \dots, n$，不过因为同学们都想摸鱼，所以 $n$ 位同学一共提出了 $q$ 个以下格式的询问：

• (k, x): $ 询问持有编号 $x 的同学在教官吹 $k$ 次哨后所在位置的下标

输入格式

第一行 1 个整数 $n$，表示参加冒泡演出的同学的数量

第二行 $n$ 个整数 $a[1 \ldots n]$，保证是一个排列，表示同学们的初始排列

第三行 1 个整数 $q$，表示同学们的询问总数

接下来 $q$ 行，每行 2 个整数 $(k, x)$ 代表一次询问

输出格式

输出 $q$ 行，每行 1 个整数代表答案

样例

样例输入 1

5
4 3 5 1 2
3
2 1
4 4
1 5

样例输出 1

2
4
5

样例输入 2

5
4 5 2 3 1
5
3 1
4 2
3 3
2 4
1 5

样例输出 2

2
2
3
4
5

数据范围与提示

• 对于 $20 \%$ 的数据，$n, q \leq 2000$。
• 对于另 $20 \%$ 的数据，$n, q \leq 10^5$，不同的 $k$ 取值不超过 20 种。
• 对于另 $20 \%$ 的数据，$n, q \leq 10^5$，不同的 $x$ 取值不超过 20 种。
• 对于另 $20 \%$ 的数据，$n, q \leq 10^5$。
• 对于 $100 \%$ 的数据，$1 \leq n, q \leq 5 \times 10^5, 1 \leq k<n, 1 \leq x \leq n$，$a[1 \ldots n]$ 保证是一个排列。

注意输入输出量较大，请使用快速的读写方式。