传统题 3000ms 256MiB

bubble

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

输入格式

第一行 1 个整数 nn,表示参加冒泡演出的同学的数量

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

第三行 1 个整数 qq,表示同学们的询问总数

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

输出格式

输出 qq 行,每行 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%20 \% 的数据,n,q2000n, q \leq 2000
  • 对于另 20%20 \% 的数据,n,q105n, q \leq 10^5,不同的 kk 取值不超过 20 种。
  • 对于另 20%20 \% 的数据,n,q105n, q \leq 10^5,不同的 xx 取值不超过 20 种。
  • 对于另 20%20 \% 的数据,n,q105n, q \leq 10^5
  • 对于 100%100 \% 的数据,$1 \leq n, q \leq 5 \times 10^5, 1 \leq k<n, 1 \leq x \leq n$,a[1n]a[1 \ldots n] 保证是一个排列。

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

CSP-S模拟测

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-10-18 8:30
结束于
2025-10-18 12:00
持续时间
3.5 小时
主持人
参赛人数
6