布伦卡即将观看今年最有趣的体育赛事——由她的朋友托尼亚组织的格斗锦标赛。
$$$n$$$ 运动员参加比赛,编号从 $$$1$$$ 到 $$$n$$$。 Burenka 将第 $$$i$$$ 位运动员的力量确定为整数 $$$a_i$$$,其中 $$$1 \leq a_i \leq n$$$。所有强度值都不同,即数组$$$a$$$是长度$$$n$$$的排列。我们知道,在一场战斗中,如果 $$$a_i > a_j$$$,那么第 $$$i$$$ 的参与者总是会赢得第 $$$j$$$ 的参与者。
锦标赛是这样进行的:最初,所有 $$$n$$$ 运动员按照 ID 升序排列,然后有无限多轮比赛。每轮只有一场战斗:队列中最前面的两个人出来战斗。胜者回到队伍前面,败者回到队伍后面。
Burenka 决定问 Tonya $$$q$$$ 问题。在每个问题中,Burenka 都会询问第 $$$i$$$ 参与者在前 $$$k$$$ 轮比赛中对于某些给定数字 $$$i$$$ 和 $$$k$$$ 获得了多少场胜利。 Tonya 不太擅长分析,所以他请你帮助他回答所有问题。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个 Burenka 的问题,打印一行包含一个整数 - 问题的答案。
示例
输入 #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
注意
在第一个测试用例中,第一个编号的运动员的实力为$$$3$$$,在第一轮中他将击败编号为$$$2$$$、实力为$$$1$$$的运动员,并在第二轮中击败编号为$$$3$$$、实力为$$$2$$$的运动员。
在第二个测试用例中,我们列出了在第一场 $$$5$$$ 比赛中参加比赛的运动员的优势:$$$1$$$ 和 $$$3$$$、$$$3$$$ 和 $$$4$$$、$$$4$$$ 和 $$$2$$$、$$$4$$$ 和 $$$1$$$、$$$4$$$ 和$$$3$$$。编号为 $$$4$$$ 的参赛者在前 $$$5$$$ 轮中赢得了 $$$0$$$ 次(他的实力为 $$$2$$$)。编号为$$$3$$$的参赛者实力为$$$4$$$,在前两场比赛中以$$$1$$$次的战斗赢得了$$$1$$$次。