CF1719C.Fighting Tournament

Burenka is about to watch the most interesting sporting event of the year — a fighting tournament organized by her friend Tonya.

$n$ athletes participate in the tournament, numbered from $1$ to $n$. Burenka determined the strength of the $i$-th athlete as an integer $a_i$, where $1 \leq a_i \leq n$. All the strength values are different, that is, the array $a$ is a permutation of length $n$. We know that in a fight, if $a_i \gt a_j$, then the $i$-th participant always wins the $j$-th.

The tournament goes like this: initially, all $n$ athletes line up in ascending order of their ids, and then there are infinitely many fighting rounds. In each round there is exactly one fight: the first two people in line come out and fight. The winner goes back to the front of the line, and the loser goes to the back.

Burenka decided to ask Tonya $q$ questions. In each question, Burenka asks how many victories the $i$-th participant gets in the first $k$ rounds of the competition for some given numbers $i$ and $k$. Tonya is not very good at analytics, so he asks you to help him answer all the questions.

布伦卡即将观看一年中最精彩的体育赛事——由她的好友托尼娅组织的一场格斗锦标赛。

共有 $n$ 名运动员参赛，编号从 $1$ 到 $n$。布伦卡将第 $i$ 名运动员的实力定义为一个整数 $a_i$，其中 $1 \leq a_i \leq n$。所有实力值互不相同，即数组 $a$ 是一个长度为 $n$ 的排列。已知在一场格斗中，若 $a_i > a_j$，则第 $i$ 名选手总是战胜第 $j$ 名选手。

锦标赛的流程如下：初始时，全部 $n$ 名运动员按其编号升序排成一列；随后进行无限轮格斗。每轮恰好进行一场比赛：队列最前面的两人出列并格斗。胜者回到队列前端，败者则排到队列末尾。

布伦卡决定向托尼娅提出 $q$ 个问题。每个问题中，布伦卡给定两个数 $i$ 和 $k$，询问第 $i$ 名运动员在比赛的前 $k$ 轮中总共获得多少场胜利。托尼娅不擅长分析计算，因此请你帮助他回答所有问题。

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \leq n \leq 10^5$, $1 \leq q \leq 10^5$) — the number of tournament participants and the number of questions.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the array $a$, which is a permutation.

The next $q$ lines of a test case contain questions. Each line contains two integers $i$ and $k$ ($1 \leq i \leq n$, $1 \leq k \leq 10^9$) — the number of the participant and the number of rounds.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 10^5$，$1 \leq q \leq 10^5$）——分别表示锦标赛参赛者人数和问题数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）——数组 $a$，它是一个排列。

每个测试用例接下来的 $q$ 行为问题。每行包含两个整数 $i$ 和 $k$（$1 \leq i \leq n$，$1 \leq k \leq 10^9$）——分别表示参赛者编号与轮数。

保证所有测试用例中 $n$ 的总和以及 $q$ 的总和均不超过 $10^5$。

For each Burenka's question, print a single line containing one integer — the answer to the question.

对于布伦卡的每个问题，请输出一行，包含一个整数——该问题的答案。

In the first test case, the first numbered athlete has the strength of $3$, in the first round he will defeat the athlete with the number $2$ and the strength of $1$, and in the second round, the athlete with the number $3$ and the strength of $2$.

In the second test case, we list the strengths of the athletes fighting in the first $5$ fights: $1$ and $3$, $3$ and $4$, $4$ and $2$, $4$ and $1$, $4$ and $3$. The participant with the number $4$ in the first $5$ rounds won $0$ times (his strength is $2$). The participant with the number $3$ has a strength of $4$ and won $1$ time in the first two fights by fighting $1$ time.

在第一个测试用例中，编号为 $1$ 的运动员力量值为 $3$；在第一轮中，他将击败编号为 $2$、力量值为 $1$ 的运动员；在第二轮中，他将击败编号为 $3$、力量值为 $2$ 的运动员。

在第二个测试用例中，我们列出前 $5$ 场比赛双方运动员的力量值：$1$ 与 $3$、$3$ 与 $4$、$4$ 与 $2$、$4$ 与 $1$、$4$ 与 $3$。编号为 $4$ 的运动员在前 $5$ 轮中获胜 $0$ 次（其力量值为 $2$）。编号为 $3$ 的运动员力量值为 $4$，在前两场比赛中参赛 $1$ 次并获胜 $1$ 次。