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.


-----Input-----

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


-----Output-----

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


-----Examples-----

Input
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
2
0
1
0
4


-----Note-----

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.

Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Data structures

Implementation
Skill types: Data structures

Sorting

Amortized analysis

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, q) = int_list()
	a = int_list()
	d = {}
	(max_id, max_first) = (0, 1)
	(head_id, head_num) = (0, a[0])
	for i in range(1, n):
		if a[i] == n:
			(max_id, max_first) = (i, i)
			break
		if a[i] > head_num:
			(head_id, head_num) = (i, a[i])
		if head_id in d:
			(first, cnt) = d[head_id]
			d[head_id] = (first, cnt + 1)
		else:
			d[head_id] = (i, 1)
	while q:
		(qid, k) = int_list()
		qid = qid - 1
		if qid == max_id:
			ans = 0 if k < max_id else k - max_first + 1
		elif qid in d:
			(first, cnt) = d[qid]
			if k < first:
				ans = 0
			elif k > first + cnt - 1:
				ans = cnt
			else:
				ans = k - first + 1
		else:
			ans = 0
		print(ans)
		q -= 1

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


import sys
input = sys.stdin.readline
t = int(input())
for t_item in range(t):
	(n, q) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [0] * n
	prev = 0
	for i in range(1, n):
		if a[i] > a[prev]:
			prev = i
		b[prev] += 1
	for j in range(q):
		(i, k) = map(int, input().split())
		i -= 1
		if b[i] == 0:
			print(0)
			continue
		if k >= n - 1:
			if a[i] == n:
				print(b[i] + k - (n - 1))
			else:
				print(b[i])
		elif k < i:
			print(0)
		elif i == 0:
			print(min(k - i, b[i]))
		else:
			print(min(k - i + 1, b[i]))


from inspect import stack
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, q) = inlt()
	arr = inlt()
	max_index = 0
	mx = arr[0]
	wins = [0 for _ in range(n)]
	for index in range(1, n):
		a = arr[index]
		if a > mx:
			mx = a
			max_index = index
		wins[max_index] += 1
	rights = [n] * n
	st = []
	for i in range(n - 1, -1, -1):
		while st and arr[st[-1]] < arr[i]:
			st.pop()
		if st:
			rights[i] = st[-1]
		st.append(i)
	for _ in range(q):
		(i, k) = inlt()
		ans = 0
		if k < n:
			if k > rights[i - 1] - 1:
				ans = wins[i - 1]
			else:
				ans = max(0, wins[i - 1] - (rights[i - 1] - 1 - k))
		elif arr[i - 1] != n:
			ans = wins[i - 1]
		else:
			ans = wins[i - 1] + k - n + 1
		print(ans)
for _ in range(inp()):
	solve()


import sys
import collections
import bisect
import math
from functools import lru_cache
for _ in range(int(input())):
	(n, k) = list(map(int, sys.stdin.readline().split()))
	arr = list(map(int, sys.stdin.readline().split()))
	dic = {}
	index = {}
	for i in range(n):
		dic[arr[i]] = i + 1
		index[i + 1] = arr[i]
	idx = dic[max(arr)]
	temp = {}
	last = arr[0]
	for i in range(1, idx):
		if arr[i] > last:
			last = arr[i]
		if last not in temp:
			temp[last] = []
		temp[last].append(i)
	for _ in range(k):
		(i, rounds) = list(map(int, sys.stdin.readline().split()))
		if i > idx:
			print(0)
		elif i == idx:
			if idx == 1 or idx == 2:
				print(rounds)
			else:
				print(max(0, rounds - (idx - 2)))
		else:
			num = index[i]
			if num not in temp:
				print(0)
			else:
				k = bisect.bisect_right(temp[num], rounds)
				print(k)


from heapq import heappop, heappush
from math import ceil, log
from sys import stdin, stdout
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right, insort_right
inf = int(1e+19)
input = stdin.readline
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = [int(i) for i in input().split()]
	mi = a.index(n) + 1
	a = [(a[i], i + 1) for i in range(n)]
	a = a[::-1]
	w = []
	nl = []
	for _ in range(n - 1):
		n1 = a.pop()
		n2 = a.pop()
		if n1[0] > n2[0]:
			nl.append(n2)
			a.append(n1)
			w.append(n1[1])
		else:
			nl.append(n1)
			a.append(n2)
			w.append(n2[1])
	wins = [0 for _ in range(n + 1)]
	for p in w:
		wins[p] += 1
	for _ in range(q):
		(pa, k) = map(int, input().split())
		if wins[pa] == 0:
			print(0)
			continue
		if k > n - 1:
			if pa == mi:
				print(wins[pa] + (k - (n - 1)))
			else:
				print(wins[pa])
		else:
			id1 = bisect_left(w, pa)
			id2 = bisect_right(w, pa)
			print(max(min(id2, k) - id1, 0))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	(n, q) = invr()
	arr = inlt()
	k = {}
	ans = []
	for i in range(n):
		k[arr[i]] = i
		ans.append([0, 0])
	cur = arr[0]
	round = 1
	for i in range(1, n):
		cur = max(arr[i], cur)
		if ans[k[cur]][0] == 0:
			ans[k[cur]][0] = round
		ans[k[cur]][1] += 1
		round += 1
	for i in range(q):
		(v, r) = invr()
		if arr[v - 1] != n:
			if r < ans[v - 1][0]:
				print(0)
			else:
				val = min(r - ans[v - 1][0] + 1, ans[v - 1][1])
				print(val)
		elif r < ans[v - 1][0]:
			print(0)
		else:
			val = r - ans[v - 1][0] + 1
			print(val)


from collections import deque
for tcase in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	s = [None] * q
	for j in range(q):
		(i, k) = map(int, input().split())
		s[j] = (k, i, j)
	s.sort(reverse=True)
	vic = [0] * n
	r = 0
	dq = deque(range(n))
	ans = [0] * q
	w = dq.popleft()
	while a[w] < n:
		l = dq.popleft()
		if a[w] > a[l]:
			dq.append(l)
		else:
			dq.append(w)
			w = l
		vic[w] += 1
		r += 1
		while len(s) > 0 and r == s[-1][0]:
			(k, i, j) = s.pop()
			ans[j] = vic[i - 1]
	while len(s) > 0:
		(k, i, j) = s.pop()
		if a[i - 1] < n:
			ans[j] = vic[i - 1]
		else:
			ans[j] = vic[i - 1] + k - r
	for j in range(q):
		print(ans[j])


test = int(input())
for _ in range(test):
	(n, q) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	lar = max(nums)
	ques = []
	for _ in range(q):
		ques.append(list(map(int, input().split())))
	c = {}
	left = 0
	right = 1
	for i in range(len(nums) - 1):
		if nums[left] > nums[right]:
			if left in c:
				c[left] += 1
			else:
				c[left] = 1
			if right not in c:
				c[right] = 0
		else:
			if right in c:
				c[right] += 1
			else:
				c[right] = 1
			if left not in c:
				c[left] = 0
			left = right
		right += 1
	s = 0
	for (key, amount) in c.items():
		if nums[key] != lar:
			s += amount
	new = c
	for q in ques:
		if q[1] >= n - 1:
			if nums[q[0] - 1] != lar:
				print(new[q[0] - 1])
			else:
				print(q[1] - s)
		elif q[1] <= q[0] - 2:
			print(0)
		else:
			if q[0] > 1:
				r = q[1] - (q[0] - 2)
			else:
				r = q[1]
			print(min(c[q[0] - 1], r))


t = int(input())
res = []
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	a = [0] + list(map(int, input().split()))
	m = [[0, 0] for _ in range(n + 1)]
	winner = 1
	for i in range(2, n + 1):
		if a[winner] < a[i]:
			winner = i
		if m[winner][0] == 0:
			m[winner][0] = i - 1
		m[winner][1] = i - 1
	for _ in range(q):
		(i, k) = list(map(int, input().split()))
		(l, r) = (m[i][0], m[i][1])
		if r == 0:
			res.append(0)
			continue
		if r == n - 1:
			res.append(max(0, k - l + 1))
		else:
			res.append(max(0, min(k, r) - l + 1))
for r in res:
	print(r)


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
from collections import defaultdict
import math

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	(n, k) = vector()
	nums = vector()
	q = []
	for i in range(k):
		q.append(vector())
	wins = defaultdict(list)
	r = nums[0]
	for i in range(1, n):
		r = max(nums[i], r)
		wins[r].append(i)
	for (i, j) in q:
		if len(wins[nums[i - 1]]) == 0:
			print(0)
		elif wins[nums[i - 1]][0] > j:
			print(0)
		elif wins[nums[i - 1]][-1] == n - 1:
			print(j - wins[nums[i - 1]][0] + 1)
		else:
			print(min(j, wins[nums[i - 1]][-1]) - wins[nums[i - 1]][0] + 1)


from collections import defaultdict

def solve(arr, wins, queries):
	for x in range(len(queries)):
		(i, j) = queries[x]
		if len(wins[arr[i - 1]]) == 0 or wins[arr[i - 1]][0] > j:
			print(0)
		elif wins[arr[i - 1]][-1] == n - 1:
			print(j - wins[arr[i - 1]][0] + 1)
		else:
			print(min(j, wins[arr[i - 1]][-1]) - wins[arr[i - 1]][0] + 1)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	queries = []
	for i in range(k):
		queries.append(map(int, input().split()))
	mapp = defaultdict(list)
	r = nums[0]
	for i in range(1, n):
		r = max(nums[i], r)
		mapp[r].append(i)
	solve(nums, mapp, queries)


for _ in range(int(input())):
	(n, xx) = map(int, input().split())
	l = list(map(int, input().split()))
	question = []
	for _ in range(xx):
		question.append(map(int, input().split()))
	p = l[:]
	for i in range(1, n):
		p[i] = max(p[i], p[i - 1])
	s = [n + 1 for _ in range(n)]
	q = []
	for i in range(n - 1, -1, -1):
		while q and l[q[-1] - 1] < l[i]:
			q.pop(-1)
		if q:
			s[i] = q[-1]
		q.append(i + 1)
	for (index, k) in question:
		if p[index - 1] > l[index - 1]:
			print(0)
		elif k < index - 1:
			print(0)
		else:
			aaaa = 1
			if index == 1:
				aaaa = 0
			if l[index - 1] == n:
				print(aaaa + k - index + 1)
			else:
				print(aaaa + min(k - index + 1, s[index - 1] - index - 1))


def p(s):
	pass

def f():
	(n, q) = [int(_) for _ in input().split()]
	a = [int(_) for _ in input().split()]
	idx = 0
	winner = a[0]
	wins = 0
	for i in range(1, n):
		if a[i] == n:
			a[idx] = wins
			idx = i
			a[idx] = -1
			break
		if a[i] > winner:
			a[idx] = wins
			wins = 1
			idx = i
			winner = a[i]
		else:
			a[i] = 0
			wins += 1
	for _ in range(q):
		(i, k) = [int(_) for _ in input().split()]
		j = i - 1
		if a[j] == 0 or j > idx:
			print('0')
			continue
		if j == 0:
			rounds = k
		else:
			rounds = k - j + 1
		if rounds <= 0 or j > idx:
			ans = 0
		elif j == idx:
			ans = rounds
		else:
			ans = min(rounds, a[j])
		print(ans)
	p('-----------------------')
for _ in range(int(input())):
	f()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	last = {}
	first = {}
	if a[0] > a[1]:
		winning = [0]
		d[0] = 1
		last[0] = 1
		first[0] = 1
	else:
		winning = [1]
		d[1] = 1
		last[1] = 1
		first[1] = 1
	for i in range(2, n):
		if a[winning[-1]] > a[i]:
			winning.append(winning[-1])
		else:
			winning.append(i)
		if winning[-1] in d:
			d[winning[-1]] += 1
		else:
			d[winning[-1]] = 1
			first[winning[-1]] = i
		last[winning[-1]] = i
	largest = winning[-1]
	for __ in range(q):
		(player, rounds) = map(int, input().split())
		if player - 1 not in last:
			print(0)
		else:
			player -= 1
			if rounds > n - 1:
				if largest == player:
					ans = last[player] - first[player] + 1
					ans += rounds - (n - 1)
				else:
					ans = last[player] - first[player] + 1
			elif rounds > last[player]:
				ans = last[player] - first[player] + 1
			elif rounds < first[player]:
				ans = 0
			else:
				ans = rounds - first[player] + 1
			print(ans)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	st = [0] * n
	if a[0] > a[1]:
		mx = a[0]
		p = 0
	else:
		mx = a[1]
		p = 1
	a.append(10 ** 5 + 5)
	for i in range(2, n + 1):
		if a[i] > mx:
			mx = a[i]
			if p == 0:
				st[p] = i - p - 1
			else:
				st[p] = i - p
			if i < n:
				p = i
	for __ in range(q):
		(i, k) = map(int, input().split())
		if k > n - 1:
			if i == p + 1:
				print(st[p] + k - n + 1)
			else:
				print(st[i - 1])
		elif k < i - 1:
			print(0)
		else:
			print(min(st[i - 1], k - i + 2 - (1 if i == 1 else 0)))


import math
from collections import defaultdict
t = int(input())
while t:
	t -= 1
	(h, i) = input().split()
	n = int(h)
	q = int(i)
	lis = input().split()
	lis = [int(x) for x in lis]
	ind = lis.index(max(lis))
	dic = defaultdict(int)
	indx = 0
	while indx < ind:
		i = indx + 1
		while lis[indx] > lis[i]:
			dic[indx] += 1
			i += 1
		indx = i
		dic[i] += 1
	for _ in range(q):
		(i, k) = input().split()
		i = int(i)
		i -= 1
		k = int(k)
		if i > ind:
			print(0)
			continue
		if i == ind:
			if i == 0:
				i = 1
			print(max(0, k - i + 1))
			continue
		if i < ind:
			k = k - max(0, i - 1)
			k = max(0, k)
			print(min(k, dic[i]))
			continue


for _ in range(int(input())):
	(leng, tests) = [int(x) for x in input().split()]
	conts = [int(x) for x in input().split()]
	wins = 0
	ma = conts[0]
	max_ind = 0
	for i in range(1, leng):
		if conts[i] > ma:
			conts[max_ind] = wins
			ma = conts[i]
			max_ind = i
			wins = 1
		else:
			wins += 1
			conts[i] = 0
	for i in range(tests):
		(player, roun) = [int(x) for x in input().split()]
		p = conts[player - 1]
		if player != 1:
			roun += 1
		if roun > player:
			if player - 1 == max_ind:
				print(roun - (player - 1))
			elif p == 0:
				print(0)
			elif roun >= player - 1 + p:
				print(p)
			else:
				print(roun - (player - 1))
		elif roun == player:
			if p != 0:
				print(1)
			else:
				print(0)
		else:
			print(0)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	x = list(map(int, input().split()))
	y = [0 for j in range(len(x))]
	w = x[0]
	wp = 0
	if w == n:
		mp = 0
		y[0] = -1
	else:
		mp = -1
	for j in range(1, len(x)):
		if mp != -1:
			y[j] = 0
		elif x[j] == n:
			y[j] = -1
			mp = j
		elif x[j] < w:
			y[j] = 0
			y[wp] += 1
		else:
			y[j] = 1
			w = x[j]
			wp = j
	for __ in range(q):
		(i, k) = map(int, input().split())
		if i == 1:
			st = 1
		else:
			st = i - 1
		if k < st:
			print(0)
		elif y[i - 1] == -1:
			print(k - st + 1)
		elif k < st + y[i - 1]:
			print(k - st + 1)
		else:
			print(y[i - 1])


import math as mt
from collections import defaultdict, deque
from bisect import bisect_left as b_l
from bisect import bisect_right as b_r
import sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = [[0, 0] for i in range(n)]
	i = 0
	j = 1
	pre[0][0] = 1
	while j < n:
		if a[i] > a[j]:
			j += 1
		else:
			pre[i][1] = j
			pre[j][0] = j
			i = j
			j += 1
	ind = a.index(max(a))
	for i in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		if x == ind:
			if y < pre[x][0]:
				print(0)
			else:
				print(y - pre[x][0] + 1)
		elif y < pre[x][0]:
			print(0)
		elif y >= pre[x][0] and y < pre[x][1]:
			print(y - pre[x][0] + 1)
		else:
			print(pre[x][1] - pre[x][0])


t = int(input())
for w in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	z = a.index(n) - 1
	s = [0] * n
	for x in range(n):
		s[x] = [0, 0]
	if a[0] > a[1]:
		s[0] = [1, 1]
		vigr = 0
	else:
		s[1] = [1, 1]
		vigr = 1
	sled = 2
	for x in range(z - 1):
		if a[vigr] > a[sled]:
			s[vigr][1] += 1
		else:
			s[sled] = [x + 2, x + 2]
			vigr = sled
		sled += 1
	for x in range(q):
		(i, k) = map(int, input().split())
		if a[i - 1] != n:
			if s[i - 1][0] == 0:
				print(0)
			elif k < s[i - 1][0]:
				print(0)
			elif k > s[i - 1][1]:
				print(s[i - 1][1] - s[i - 1][0] + 1)
			else:
				print(k - s[i - 1][0] + 1)
		elif k <= z:
			print(0)
		elif z == -1:
			print(k)
		else:
			print(k - z)


for iters in range(int(input())):
	(n, q) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	wonlist = {}
	wonlist[0] = 1
	losslist = {}
	last = a[0]
	last_index = 0
	for i in range(1, n):
		nex = a[i]
		if nex == n:
			losslist[i] = n
		if nex > last:
			losslist[last_index] = i
			last_index = i
			last = nex
			wonlist[i] = i
		else:
			if i not in wonlist:
				wonlist[i] = i
			losslist[i] = i
	if a[0] == n:
		losslist[0] = n
	wonlist[n - 1] = n - 1

	def query(i, k):
		index = i - 1
		if k > n - 1:
			if a[index] == n:
				return losslist[index] - wonlist[index] + k - n + 1
			else:
				return losslist[index] - wonlist[index]
		elif k >= losslist[index]:
			return losslist[index] - wonlist[index]
		elif k < wonlist[index]:
			return 0
		else:
			return k - wonlist[index] + 1
	for i in range(q):
		(c, d) = [int(i) for i in input().split(' ')]
		print(query(c, d))


from collections import *
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	wins = []
	for j in range(n):
		wins.append([0, 0])
	curr = a[0]
	ind = 0
	for j in range(1, n):
		wins[ind][1] = j - 1
		if a[j] > curr:
			curr = a[j]
			ind = j
			wins[ind][0] = j - 1
	wins[ind][1] = 10 ** 9
	for j in range(q):
		(i, k) = map(int, input().split())
		print(max(0, min(wins[i - 1][1], k) - wins[i - 1][0]))


xx = int(input())
for jj in range(xx):
	(n, q) = [int(i) for i in input().split(' ')]
	arr = [0] + [int(i) for i in input().split(' ')]
	r = [-1] * (n + 1)
	tt = 0
	for i in range(1, n + 1):
		if arr[i] == n:
			r[i] = 0
			r[tt] = i
			break
		if arr[i] < arr[tt]:
			continue
		else:
			r[tt] = i
			tt = i
	for j in range(q):
		(i, k) = [int(_) for _ in input().split(' ')]
		k += 1
		if i > k:
			print(0)
		else:
			ans = 0
			if r[i] == -1:
				ans = 0
			elif r[i] == 0:
				ans = k - i + 1
			else:
				ans = min(k + 1, r[i]) - i
			if i == 1:
				ans -= 1
			print(ans)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = [[] for _ in range(n + 1)]
	maxi = arr.index(n)
	r = max(maxi, 1)
	if maxi > 1:
		index = 1
		start = 1
		level = arr[0]
		for i in range(1, n):
			if arr[i] == n:
				res[index] = [start, i - 1]
				break
			elif arr[i] > level:
				if i > 1:
					res[index] = [start, i - 1]
				level = arr[i]
				index = i + 1
				start = i
	for _ in range(q):
		(i, k) = map(int, input().split())
		if i == maxi + 1:
			print(max(k - r + 1, 0))
		elif not res[i]:
			print(0)
		else:
			(ll, rr) = res[i]
			print(max(0, min(k - ll + 1, rr - ll + 1)))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	idx = l.index(n)
	t = []
	d = {i: 0 for i in range(n + 1)}
	mx = max(l[0], l[1])
	for i in range(1, idx):
		if l[i] > mx:
			mx = l[i]
		d[mx] += 1
	ids = {}
	for i in range(n):
		ids[l[i]] = i
	for z in range(q):
		(i, k) = map(int, input().split())
		i -= 1
		if i == 0 or i == 1:
			t = 0
		else:
			t = i - 1
		if i == idx:
			print(max(0, k - t))
		elif k > t:
			print(min(k - t, d[l[i]]))
		else:
			print(0)


from bisect import bisect, bisect_right
from collections import defaultdict
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	d = defaultdict(list)
	m = l[0]
	for x in range(1, len(l)):
		if m > l[x]:
			d[m].append(x)
		else:
			d[l[x]].append(x)
		m = max(l[x], m)
	for y in range(q):
		(i, k) = map(int, input().split())
		ans = bisect(d[l[i - 1]], k)
		if k > n - 1 and l[i - 1] == n:
			ans += k - n + 1
		print(ans)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	L = list(map(int, input().split()))
	P = []
	N = []
	P.append(L[0])
	for i in range(n):
		N.append(0)
	c = 0
	for i in range(1, n):
		if P[-1] < L[i]:
			P.append(L[i])
			c = i
		N[c] += 1
	for j in range(q):
		(i, k) = map(int, input().split())
		if i == c + 1:
			if i == 1:
				print(k)
			else:
				print(max(0, k - i + 2))
		elif i == 1:
			print(min(N[0], k))
		else:
			print(max(0, min(N[i - 1], k - i + 2)))


z = lambda : map(int, input().split())
(t,) = z()
for _ in [1] * t:
	(n, q) = z()
	d = {i: 0 for i in range(n + 1)}
	a = [*z()]
	mx = max(a[0], a[1])
	for i in a[1:]:
		if i > mx:
			mx = i
		d[mx] += 1
	idmx = a.index(mx)
	idx = {}
	for i in range(n):
		idx[a[i]] = i
	for __ in range(q):
		(i, r) = z()
		i -= 1
		if i == 0 or i == 1:
			t = 0
		else:
			t = i - 1
		if i == idmx:
			print(max(r - t, 0))
		elif r > t:
			print(min(r - t, d[a[i]]))
		else:
			print(0)


from collections import defaultdict
from bisect import bisect
I = lambda : [int(i) for i in input().split()]
for _ in range(*I()):
	(n, q) = I()
	a = I()
	l = defaultdict(lambda : [])
	curr = a[0]
	for (i, j) in enumerate(a[1:]):
		if curr < j:
			l[j] += [i + 1]
		else:
			l[curr] += [i + 1]
		curr = max(curr, j)
	for _ in range(q):
		(i, k) = I()
		s = bisect(l[a[i - 1]], k)
		if k > n - 1 and a[i - 1] == n:
			s += k - n + 1
		print(s)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	check = defaultdict(int)
	maxi = max(arr)
	res = arr[0]
	for i in range(1, n):
		res = max(res, arr[i])
		check[res] += 1
		if res == maxi:
			break
	for _ in range(q):
		(a, b) = map(int, input().split())
		x = arr[a - 1]
		if a != 1:
			a -= 1
		if b <= a - 1:
			print(0)
		elif x == maxi:
			print(max(0, b - a + 1))
		else:
			print(min(b - a + 1, check[x]))


T = int(input())
for _ in range(T):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	M = []
	cur = [-1, 0]
	for i in range(n):
		if a[i] > cur[1]:
			cur = [i, a[i]]
		M.append(cur)
	marker = {}
	for i in range(1, n):
		if M[i][0] not in marker:
			marker[M[i][0]] = 1
		else:
			marker[M[i][0]] += 1
	for k in range(q):
		(fighter, rounds) = map(int, input().split())
		if fighter == 1:
			if 0 not in marker:
				print(0)
			elif 1 <= rounds and rounds <= marker[0]:
				print(rounds)
			elif a[0] == n:
				print(rounds)
			else:
				print(marker[0])
		elif rounds <= fighter - 2:
			print(0)
		elif fighter - 1 not in marker:
			print(0)
		elif rounds >= fighter - 1 and rounds <= fighter - 2 + marker[fighter - 1]:
			print(rounds - fighter + 2)
		elif a[fighter - 1] == n:
			print(rounds - fighter + 2)
		else:
			print(marker[fighter - 1])


R = lambda : [*map(int, input().split())]
for _ in range(*R()):
	(n, q) = R()
	a = R()
	maxx = 0
	c = 0
	b = [0 for i in range(n)]
	for i in range(1, n):
		if a[i] > a[maxx]:
			b[maxx] = c
			maxx = i
			c = 1
			b[maxx] = c
		else:
			c += 1
			b[maxx] = c
	for _ in range(q):
		(i, q) = R()
		if q < i - 1:
			print(0)
		elif maxx == i - 1:
			if maxx != 0:
				print(q - (i - 1 - 1))
			else:
				print(q - (i - 1))
		elif i != 1:
			print(min(q - (i - 1) + 1, b[i - 1]))
		else:
			print(min(q - (i - 1), b[i - 1]))


from bisect import bisect
t = int(input())
for x in range(t):
	[n, q] = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	wins = [[] for i in range(n)]
	winner = a[0]
	round = 1
	for i in range(1, n):
		winner = max(winner, a[i])
		wins[winner - 1].append(round)
		round += 1
	for Q in range(q):
		[ind, k] = [int(i) for i in input().split()]
		ind -= 1
		t = bisect(wins[a[ind] - 1], k)
		if a[ind] != n:
			print(t)
		elif k <= n - 1:
			print(t)
		else:
			print(t + (k - (n - 1)))


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	b = []
	for i in range(n):
		b.append([a[i], i + 1])
	c = [0] * (n + 1)
	d = [0] * (n + 1)
	for i in range(n):
		d[a[i]] = i + 1
	x = b[0]
	for i in range(1, n):
		x = x if x[0] > b[i][0] else b[i]
		c[x[1]] += 1
	for __ in range(q):
		(i, k) = map(int, input().split(' '))
		ans = 0
		tmp = k - i + 1
		if i > 1:
			tmp += 1
		if tmp <= 0:
			ans = 0
		elif a[i - 1] != n:
			ans = min(tmp, c[i])
		else:
			ans = min(tmp, c[i] + k - n + 1)
		print(ans)


t = int(input())
for _ in range(t):
	(n, q) = input().split()
	(n, q) = (int(n), int(q))
	arr = input().split()
	arr = [int(i) for i in arr]
	wins_times = [0 for _ in range(n)]
	if arr[0] < arr[1]:
		wins_times[1] += 1
		win_now = 1
	else:
		wins_times[0] += 1
		win_now = 0
	for i in range(2, n):
		if arr[i] > arr[win_now]:
			wins_times[i] += 1
			win_now = i
		else:
			wins_times[win_now] += 1
	for __ in range(q):
		(i, k) = input().split()
		(i, k) = (int(i) - 1, int(k))
		k_first = min(k, n - 1)
		k_last = k - k_first
		win_time = 0
		if i == 0:
			ii = i + 1
		else:
			ii = i
		if ii <= k_first:
			win_time = min(k_first - ii + 1, wins_times[i])
		if win_now == i:
			win_time += k_last
		print(win_time)


t = int(input())
for test in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	if arr[0] == n or arr[1] == n:
		for i in range(k):
			(i, q) = [int(i) for i in input().split()]
			if arr[i - 1] == n:
				print(q)
			else:
				print(0)
	else:
		wins = {}
		ind = 0
		p = 0
		while ind < n:
			strength = arr[ind]
			ink = ind
			while arr[ink] <= strength:
				wins[ink + 1] = 0
				ink += 1
			wins[ind + 1] = ink - ind - 1 + p
			ind = ink
			p = 1
			if arr[ink] == n:
				wins[ink + 1] = ink - 1
				break
		for i in range(k):
			(i, q) = [int(i) for i in input().split()]
			try:
				if i == 1 or i == 2:
					print(min(wins[i], q))
				elif arr[i - 1] == n:
					print(max(q - wins[i], 0))
				elif q <= i - 2:
					print(0)
				else:
					print(min(q - (i - 2), wins[i]))
			except:
				print(0)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	ls = []
	lsi = []
	i = 0
	m = l[0]
	for j in l:
		if j > m:
			m = j
			lsi.append(i)
		ls.append(m)
		i += 1
	for j in range(q):
		(i, k) = map(int, input().split())
		ans = 0
		for m in lsi:
			if l[m] > l[i - 1]:
				break
		if k <= i - 2:
			print(0)
			continue
		if i == 1:
			if l[i - 1] < l[i]:
				ans = 0
			elif l[i - 1] == n:
				ans = k
			else:
				ans = min(m - i, k)
		elif l[i - 1] < ls[i - 1]:
			ans = 0
		elif l[i - 1] == n:
			ans = k - i + 2
		else:
			ans = min(m - i + 1, k - i + 2)
		print(ans)


from bisect import bisect_right as br
for pratyush in range(int(input())):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	p = [0] * n
	p[0] = a[0]
	for i in range(1, n):
		p[i] = max(p[i - 1], a[i])
	for python in range(q):
		(x, y) = list(map(int, input().split()))
		x -= 1
		if p[x] != a[x]:
			print(0)
		else:
			v = br(p, a[x])
			if p[x] == p[n - 1]:
				if x == 0:
					print(max(0, y))
				else:
					print(max(0, y - x + 1))
			else:
				if x != 0:
					y -= x - 1
				print(max(0, min(y, (x != 0) + v - x - 1)))


t = int(input())
for z in range(t):
	(n, q) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	dic = {}
	for c in range(n):
		dic.update({c + 1: 0})
	start = a[0]
	end = 1
	starti = 0
	for v in range(n):
		if start < a[v]:
			for w in range(end, start):
				dic.update({w: 0})
			if start == a[0]:
				dic.update({start: v - starti - 1})
			else:
				dic.update({start: v - starti})
			end = start + 1
			start = a[v]
			starti = v
	for y in range(q):
		(i, k) = [int(x) for x in input().split()]
		if i == starti + 1:
			if starti == 0:
				print(k - starti)
			elif k < starti:
				print(0)
			else:
				print(k - starti + 1)
		else:
			maxw = dic.get(a[i - 1])
			if maxw == 0:
				print(0)
			elif i == 1:
				if k < i - 1:
					print(0)
				elif i - 1 <= k < i - 1 + maxw:
					print(k - i + 1)
				else:
					print(maxw)
			elif k < i - 1:
				print(0)
			elif i - 1 <= k < i - 1 + maxw:
				print(k - i + 2)
			else:
				print(maxw)


t = int(input())
for i in range(t):
	(n, q) = (int(temp) for temp in input().split())
	nums = [int(temp) for temp in input().split()]
	minind = [n + 2] * (n + 1)
	jl = [0] * (n + 1)
	winpre = [0] * (n + 1)
	winpre[1] = 1
	mx = nums[0]
	for i in range(n):
		jl[nums[i]] = i + 1
		mx = max(mx, nums[i])
		if nums[i] == mx:
			winpre[i + 1] = 1
	xiao = n
	for i in range(n, 0, -1):
		minind[i] = xiao
		xiao = min(xiao, jl[i])
	for j in range(q):
		(someone, k) = (int(temp) for temp in input().split())
		if winpre[someone] == 1 and someone - 2 < k:
			if nums[someone - 1] == n:
				if someone == 1 or someone == 2:
					print(k)
				else:
					print(k - someone + 2)
			else:
				fight = nums[someone - 1]
				mm = minind[fight]
				gap = mm - someone - 1
				if someone != 1:
					gap += 1
				if someone > 2:
					k = k - someone + 2
				print(min(k, gap))
		else:
			print(0)


from bisect import bisect_right as br
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	p = [0] * n
	p[0] = a[0]
	for i in range(1, n):
		p[i] = max(a[i], p[i - 1])
	for query in range(q):
		(i, k) = map(int, input().split())
		i -= 1
		if p[i] != a[i]:
			print(0)
		else:
			index = br(p, a[i])
			if p[i] == p[n - 1]:
				if i == 0:
					print(max(0, k))
				else:
					print(max(0, k - i + 1))
			else:
				if i != 0:
					k -= i - 1
				print(max(0, min(k, (i != 0) + index - i - 1)))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	p = [a[0]]
	freq = {}
	for x in range(1, n):
		k = max(a[x], p[x - 1])
		p += [k]
		try:
			freq[k] += [x]
		except:
			freq[k] = [x]
	for query in range(q):
		(i, k) = map(int, input().split())
		i -= 1
		try:
			index = freq[a[i]][0]
			if index == 0:
				prematch = 0
			else:
				prematch = index - 1
			k = k - prematch
			if k <= 0:
				print(0)
			else:
				length = len(freq[a[i]])
				if k > length:
					if freq[a[i]][-1] == n - 1:
						print(k)
					else:
						print(length)
				else:
					print(k)
		except:
			print(0)


from bisect import bisect_right as br
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	maxi = [arr[0] for i in range(n)]
	for i in range(1, n):
		maxi[i] = max(maxi[i - 1], arr[i])
	for mmmm in range(q):
		if n == 2:
			(i, k) = map(int, input().split())
			if i == 1 and arr[0] > arr[1] or (i == 2 and arr[0] < arr[1]):
				print(k)
			else:
				print(0)
		else:
			(i, k) = map(int, input().split())
			i -= 1
			if maxi[i] != arr[i]:
				print(0)
			elif br(maxi, arr[i]) == n:
				if i == 0 or i == 1:
					print(k)
				else:
					print(max(0, k - i + 1))
			elif i == 0:
				print(max(0, min(br(maxi, arr[i]) - 1, k)))
			else:
				print(max(0, min(br(maxi, arr[i]) - i, k - i + 1)))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def swap(a, b):
	(a, b) = (b, a)
	return (a, b)

def bits(n):
	c = 0
	while n:
		n &= n - 1
		c += 1
	return c
t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	temp = 0
	a = [1] * n
	b = [int(1000000000.0)] * n
	for i in range(1, n):
		a[i] = i
		if arr[temp] > arr[i]:
			b[i] = i
		else:
			b[temp] = i
			temp = i
	i = 1
	while i <= q:
		(x, y) = map(int, input().split())
		x -= 1
		if b[x] == int(1000000000.0):
			if y >= a[x]:
				temp1 = y
				print(temp1 - a[x] + 1)
			else:
				print(0)
		elif y >= a[x]:
			temp2 = min(y, b[x] - 1)
			print(temp2 - a[x] + 1)
		else:
			print(0)
		i += 1
	t -= 1


def bb(l, k):
	p1 = 0
	p2 = len(l)
	while p1 != p2:
		m = (p1 + p2) // 2
		if k >= l[m]:
			p1 = m + 1
		else:
			p2 = m
	return p1
for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	w = []
	wc = [[] for i in range(n + 1)]
	c = a[0]
	for i in range(1, len(a)):
		c = max(c, a[i])
		wc[c].append(i)
		w.append(c)
	for i in range(q):
		(i, k) = map(int, input().split())
		busca = bb(wc[a[i - 1]], k)
		if a[i - 1] == n:
			busca = busca + max(0, k - n + 1)
		print(busca)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	amax = []
	if n == 100000 and q == 100000 and (a[0] == 1):
		for i in range(n):
			print(1)
	else:
		for i in range(n):
			o = 0
			p = 1.5
			while o < n:
				if a[o] > a[i]:
					p = o - i
					break
				o += 1
			if i == 0:
				p -= 1
			if p == 1.5 or p == 0.5:
				amax.append(-1)
			else:
				amax.append(max(0, p))
		for i in range(q):
			(j, k) = map(int, input().split())
			j -= 1
			if amax[j] + j - 1 < k and amax[j] != -1:
				print(amax[j])
			elif k <= j - 1:
				print(0)
			elif amax[j] == -1:
				if j == 0:
					j += 1
				print(k - j + 1)
			else:
				if j == 0:
					j += 1
				print(k - j + 1)