22928번 - Permutation CFG 다국어

문제

Consider a permutation of the integers 1ドル$ to $n$. Now, consider each number 1ドル$ through $n$ to be a non-terminal in a Context-Free Grammar (CFG). Each number $k$ expands a list of the integers from 1ドル$ to $k$ in the order of the permutation. For example, if $n=4$ and the permutation is 1ドル$ 4ドル$ 3ドル$ 2ドル$:

• 1ドル \implies 1$
• 2ドル \implies 1$ 2ドル$
• 3ドル \implies 1$ 3ドル$ 2ドル$
• 4ドル \implies 1$ 4ドル$ 3ドル$ 2ドル$

Now, consider a process of starting with $n,ドル and at each step, applying these rules to create a new list of integers. In the above example, at the first step:

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

At the second step:

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

At the third step:

$$ \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}$$

Given a permutation, a number of steps, and a list of queries asking for the number of occurrences of a particular integer in a prefix of the list created by the process, answer all of the queries.

입력

The first line of input contains three integers, $n$ (2ドル \le n \le 10^5$), $s$ (1ドル \le s \le 5 $) and \mbox{$q$ (1ドル \le q \le 2 \cdot 10^5$)}, where $n$ is the size of the permutation, $s$ is the number of steps to apply the process, and $q$ is the number of queries.

Each of the next $n$ lines contains a single integer $p$ (1ドル \le p \le n$). This is the permutation, in order. All of the values of $p$ will be distinct.

Each of the next $q$ lines contains two integers $k$ (1ドル \le k \le n$) and $a$ (1ドル \le a \le 10^{9},ドル $a$ will not exceed the length of the final list). This is a query for the number of occurrences of the integer $k$ in the first $a$ elements of the list created by the process.

출력

Output $q$ lines, each with a single integer, which are the answers to the queries in the order that they appear in the input.

제한

힌트