[Solution] Fighting Tournament solution codeforces

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

Table of Contents

Fighting Tournament solution codeforces

𝑛n athletes participate in the tournament, numbered from 11 to 𝑛n. Burenka determined the strength of the 𝑖i-th athlete as an integer 𝑎𝑖ai, where 1𝑎𝑖𝑛1≤ai≤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 𝑎𝑖>𝑎𝑗ai>aj, 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.

Fighting Tournament solution codeforces

The first line contains one integer 𝑡t (1𝑡1041≤t≤104) — 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𝑛1052≤n≤1051𝑞1051≤q≤105) — the number of tournament participants and the number of questions.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤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𝑖𝑛1≤i≤n1𝑘1091≤k≤109) — 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 105105.

Output

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

Fighting Tournament solution codeforces

Example
input

Copy
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
output

Copy
2
0
1
0
4

Fighting Tournament solution codeforces

In the first test case, the first numbered athlete has the strength of 33, in the first round he will defeat the athlete with the number 22 and the strength of 11, and in the second round, the athlete with the number 33 and the strength of 22.

In the second test case, we list the strengths of the athletes fighting in the first 55 fights: 11 and 3333 and 4444 and 2244 and 1144 and 33. The participant with the number 44 in the first 55 rounds won 00 times (his strength is 22). The participant with the number 33 has a strength of 44 and won 11 time in the first two fights by fighting 11 time.

For Solution

“Click Here”

Leave a Comment