题目来自 CCSP2025 T3，评测使用官方数据。

经核查，原始题面和场上勘误的数据范围描述远大于官方数据，因此对数据范围进行修正。

时间限制： 1.0 秒

空间限制： 512 MiB

题目描述

公司的云端计算平台采用 Serverless 架构。服务器无感知计算（Serverless Computing）是一种主流云计算范式，其核心特征是开发者无需管理底层服务器，由云平台根据实际需求动态分配资源并运行代码。开发者只需编写函数（Function），云平台会自动负责函数的部署、调度与伸缩。现在有一个函数到达的序列，$f_1,f_2,\cdots,f_N$，每个函数有一个属性值 $a_1,a_2,\cdots,a_N$。每个函数的属性值互不相同，且恰好构成一个 $1\sim N$ 的排列。作为平台需要根据资源合理的排列这些函数，因此涉及到函数的重新编排。重新编排函数是复杂的，为了简单理解，本题中重新编排的操作简化为在原序列中选择一系列不相交的区间 $[L_i,R_i]$ 并且将每一个区间各自反转，其代价为 $\sum R_i-\sum L_i$。显然，满足代价不超过 $c$ 的操作后序列有很多个。我们希望进行 $Q$ 次查询，查询按照字典顺序排序不重复的第 $i$ 个序列的第 $j$ 个 Serverless 函数的属性数值。特别地，这里的序列编号指的在符合本题条件中的所有序列的编号，并非在全排列中的序号。

输入格式

从标准输入读入数据。

本题包含多组测试数据。

第一行输入一个整数 $T$ 代表测试的组数。

对于每组测试数据：

第一行包括三个整数 $N,c,Q$。分别代表 Serverless 函数的个数，操作代价上限和总查询次数。接下来一行包含 $N$ 个数，为 Serverless 函数的属性值。随后紧接 $Q$ 行查询，每一行有两个整数 $i,j$ 描述查询。

输出格式

输出到标准输出。

对于每组测试数据：

输出 $Q$ 行，对于每一个查询请求，输出查询的结果。特别地，如果不存在第 $i$ 个序列，输出 $-1$。

1
3 1 4
1 2 3
1 1
2 2
3 3
59 1

1
3
3
-1

样例 1 解释

在样例中，有 $3$ 个 Serverless 函数。满足交换数值不超过 $1$ 的合法排序只有 $1,2,3$、$1,3,2$、$2,1,3$。因此，查询第一个序列的第一个数为 $1$，查询第二个序列的第 $2$ 个数为 $3$，第三个序列的第三个数为 $3$。第 $59$ 个序列不存在，输出 $-1$。

子任务

对于所有数据，保证：

• $N,Q\le 10^5,\ \sum N,\sum Q\le 5\times 10^5,\ 1\le c\le 4$；
• $1\le i\le 10^{9},\ 1\le j\le N$；
• $a_1,a_2,\cdots,a_N$ 恰好构成一个 $1\sim N$ 的排列。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

来源

CF1470E - Strange Permutation