题目描述

考虑 $1$ 到 $n$ 的一个排列。现在，将 $1$ 到 $n$ 的每个数字视为一个 上下文无关文法（CFG）中的非终结符。每个数字 $k$ 会展开为从 $1$ 到 $k$ 的整数列表，其顺序由该排列决定。例如，若 $n = 4$ 且排列为 $1\ 4\ 3\ 2$：

$$\begin{aligned} 1 & \Longrightarrow 1 \\ 2 & \Longrightarrow 1\ 2 \\ 3 & \Longrightarrow 1\ 3\ 2 \\ 4 & \Longrightarrow 1\ 4\ 3\ 2 \end{aligned}$$

现在考虑如下过程：从 $n$ 开始，每一步都应用上述规则，将当前列表中的每个数字替换为其对应的展开式，从而得到一个新的整数列表。在上面的例子中，第一步的结果为：

$$\overbrace{1\ 4\ 3\ 2}^{4}$$

第二步的结果为：

$$\overbrace{1}^{1}\ \overbrace{1\ 4\ 3\ 2}^{4}\ \overbrace{1\ 3\ 2}^{3}\ \overbrace{1\ 2}^{2}$$

第三步的结果为：

$$\overbrace{1}^{1}\ \overbrace{1}^{1}\ \overbrace{1\ 4\ 3\ 2}^{4}\ \overbrace{1\ 3\ 2}^{3}\ \overbrace{1\ 2}^{2}\ \overbrace{1}^{1}\ \overbrace{1\ 3\ 2}^{3}\ \overbrace{1\ 2}^{2}\ \overbrace{1}^{1}\ \overbrace{1\ 2}^{2}$$

给定一个排列、执行的步数，以及若干询问，每个询问要求回答在过程最终生成的列表中，某个特定整数在列表前若干个位置中出现的次数。请回答所有询问。

输入格式

输入的第一行包含三个整数 $n$（$2 \le n \le 10^5$）、$s$（$1 \le s \le 5$）和 $q$（$1 \le q \le 2 \cdot 10^5$），其中 $n$ 是排列的长度，$s$ 是过程执行的步数，$q$ 是询问的数量。

接下来 $n$ 行，每行包含一个整数 $p$（$1 \le p \le n$）。这些数按顺序构成给定的排列。所有 $p$ 的值互不相同。

接下来 $q$ 行，每行包含两个整数 $k$（$1 \le k \le n$）和 $a$（$1 \le a \le 10^9$，且 $a$ 不会超过最终列表的长度）。这是一个询问，要求回答在过程生成的列表中，前 $a$ 个元素中整数 $k$ 出现的次数。

输出格式

输出 $q$ 行，每行一个整数，按输入顺序依次输出每个询问的答案。

4 3 6
1
4
3
2
1 6
2 20
4 1
3 5
2 9
1 1

3
6
0
1
2
8

提示

翻译由 DeepSeek V3.2 完成