### 问题描述 小然有一个长度为 $N$ 的整数数组 $A$。 数组中索引 $i$ 的排名定义为 $L+1$，其中 $L$ 是数组中大于 $A_i$ 的元素的数量。 现在，小然有 $Q$ 个查询，每个查询包含两个整数 $K$ 和 $R$。他的任务是找到最小的整数 $X$，满足如果从子数组 $A[1, K-1]$ 和子数组 $A[K+1, N]$ 中移除至多 $X$ 个元素，原数组中索引为 $K$ 的元素的排名就小于等于 $R$。 注意： - $A[P, Q]$ 表示的子数组为 $[A_P, A_{P+1}, ..., A_{Q-1}, A_Q]$。 - 所有的查询都是相互独立的。 ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包含多行： - 第一行输入两个整数 $N$ 和 $Q$，表示数组的长度和查询的数量。 - 第二行输入 $N$ 个整数，分别是 $A_1$，$A_2$，...，$A_N$，表示数组 $A$。 - 接下来 $Q$ 行，每行输入两个整数 $K$ 和 $R$，表示一个查询。 ### 输出格式 对于每个查询，输出一行，表示为了让原数组中索引为 $K$ 的元素的排名小于等于 $R$，需要移除的元素的最小数量。 ### 样例输入 ```markdown 1 4 5 2 1 3 4 1 1 1 2 2 1 2 2 3 2 ``` ### 样例输出 ```markdown 2 1 2 1 0 ``` ### 说明 样例中的第一个查询：我们可以从子数组 $A[2, 4]$ 中移除索引为 $3$ 和 $4$ 的元素。此时，数组变为 $[2, 1]$，原数组中索引为 $1$ 的元素在现在的数组中的排名为 $1$。 样例中的第二个查询：我们可以从子数组 $A[2, 4]$ 中移除索引为 $4$ 的元素。此时，数组变为 $[2, 1, 3]$，原数组中索引为 $1$ 的元素在现在的数组中的排名为 $2$。 样例中的第五个查询：原数组中索引为 $3$ 的元素在现在的数组中的排名就等于 $2$，因此我们不需要移除任何元素。 ### 评测数据范围 $1 \leq T \leq 10^4$。 $1 \leq N, Q \leq 10^5$。 $1 \leq K, R \leq N$。 $-10^9 \leq A_i \leq 10^9$。 所有测试用例中 $N$ 和 $Q$ 的和不超过 $2 \times 10^5$。