Fighting Tournament

题意翻译

## 题意 Burenka正准备去观看一年中最有趣的体育活动 —— 她朋友Tonya组织的格斗锦标赛。 有 **n** 名运动员参加了大赛，标号分别为为 1，2，... ，n 。第 **i** 名运动员的实力是 **$a_i（1 \le a_i \le n）$** 。**每个运动员的实力是不同的，也就是说，数组 a 是 n 的 一种 全排列** 。 大赛的流程是这样的： 一开始，运动员们**按标号从小到大**排成一列，队头为 **1** 号运动员，队尾为 **n** 号运动员。 每轮一次比赛，**队头**的两个人进行格斗，**赢的人（实力较强的人）变成队头，输的人变成队尾** 。 Burenka 问了 Tonya **q** 个问题，每个问题包含两个整数 **i** 和 **k** ，表示 **i 号运动员在前 k 轮中会胜多少场**。 ### 输入格式 第一行一个整数 **t** $(1\le t\le 10^4)$，表示数据组数。 对于每组数据： 第一行两个整数 **n** 和 **q** $(2\le n \le 10^5,1\le q\le 10^5)$，表示 参加大赛的运动员数量 和 问题数量。 第二行 **n** 个整数 **$a_1,a_2,...,a_n(1\le a_i\le n)$**，表示数组 **a**，而且是个 **全排列**。 接下来的 **q** 行表示每个问题，每行两个整数 **i** 和 **k** $(1\le i\le n,1\le k\le 10^9)$，表示**运动员的标号** 和 **轮数**。 ### 输出格式 对于每个问题，一行一个整数表示 **问题的答案**。

题目描述

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 > 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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

3
3 1
3 1 2
1 2
4 2
1 3 4 2
4 5
3 2
5 2
1 2 3 5 4
5 1000000000
4 6

输出样例 #1

2
0
1
0
4

说明

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.

题目大意：

布伦卡准备观看一年中最有趣的体育活动——她朋友托妮亚组织的格斗锦标赛。

有 n 名运动员参加了大赛，标号分别为 1，2，... ，n 。第 i 名运动员的实力是 $ a_i $（1 ≤ $ a_i $ ≤ n）。每个运动员的实力是不同的，也就是说，数组 a 是 n 的一个全排列。

大赛的流程是这样的：

一开始，运动员们按标号从小到大排成一列，队头为 1 号运动员，队尾为 n 号运动员。

每轮一次比赛，队头的两个人进行格斗，赢的人（实力较强的人）变成队头，输的人变成队尾。

布伦卡问了托妮亚 q 个问题，每个问题包含两个整数 i 和 k ，表示 i 号运动员在前 k 轮中会胜多少场。

输入格式：

第一行一个整数 t（1≤ t ≤ 10^4），表示数据组数。

对于每组数据：

第一行两个整数 n 和 q（2≤ n ≤ 10^5，1≤ q ≤ 10^5），表示参加大赛的运动员数量和问题数量。

第二行 n 个整数 $ a_1, a_2, ..., a_n $（1≤ $ a_i $ ≤ n），表示数组 a，而且是个全排列。

接下来的 q 行表示每个问题，每行两个整数 i 和 k（1≤ i ≤ n，1≤ k ≤ 10^9），表示运动员的标号和轮数。

输出格式：

对于每个问题，一行一个整数表示问题的答案。题目大意： 布伦卡准备观看一年中最有趣的体育活动——她朋友托妮亚组织的格斗锦标赛。 有 n 名运动员参加了大赛，标号分别为 1，2，... ，n 。第 i 名运动员的实力是 $ a_i $（1 ≤ $ a_i $ ≤ n）。每个运动员的实力是不同的，也就是说，数组 a 是 n 的一个全排列。 大赛的流程是这样的： 一开始，运动员们按标号从小到大排成一列，队头为 1 号运动员，队尾为 n 号运动员。 每轮一次比赛，队头的两个人进行格斗，赢的人（实力较强的人）变成队头，输的人变成队尾。 布伦卡问了托妮亚 q 个问题，每个问题包含两个整数 i 和 k ，表示 i 号运动员在前 k 轮中会胜多少场。 输入格式： 第一行一个整数 t（1≤ t ≤ 10^4），表示数据组数。 对于每组数据： 第一行两个整数 n 和 q（2≤ n ≤ 10^5，1≤ q ≤ 10^5），表示参加大赛的运动员数量和问题数量。 第二行 n 个整数 $ a_1, a_2, ..., a_n $（1≤ $ a_i $ ≤ n），表示数组 a，而且是个全排列。 接下来的 q 行表示每个问题，每行两个整数 i 和 k（1≤ i ≤ n，1≤ k ≤ 10^9），表示运动员的标号和轮数。 输出格式： 对于每个问题，一行一个整数表示问题的答案。