题目描述

给定长度为 $n$ 的整数序列 $a_{1\sim n}$，定义 $a_i$ 的排名为 $(l+1)$，其中 $l$ 是数组中满足 $a_j > a_i$ 的下标 $j$ 的数量。注意，可能有多个 $a_i$ 具有相同的排名。

你需要回答 $q$ 个查询，每个查询的形式如下：

• k r：给定整数 $k$ 和 $r$（$1 \leq k, r \leq n$），找到最小的非负整数 $x$，使得如果从子数组 $a[1, k-1]$ 中移除至多 $x$ 个元素，并且从子数组 $a[k+1, n]$ 中移除至多 $x$ 个元素，那么在原始数组中 $a_k$ 的排名小于等于 $r$。

注意：$a[l, r]$ 表示子数组 $[a_l, a_{l+1}, \ldots, a_r]$，每个查询之间是独立的。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $a_{1\sim n}$。

接下来 $q$ 行，每行两个整数 $k,r$ 表示一次询问的参数。

输出格式

共 $q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案。

4 5
2 1 3 4
1 1
1 2
2 1
2 2 
3 2

2
1
2
1
0

样例解释 1

在第一次询问中，需要把 a3=3,a4=4 均移除才能使得 a1 的排名为 1，故答案为 2。

数据范围

对于 $30\%$ 的数据，$1\leq n,q\leq 20$。

对于 $60\%$ 的数据，$1\leq n,q\leq 5000$。

对于 $100\%$ 的数据，$1\leq n,q\leq 2\times 10^5$，$-10^9\leq a_i\leq 10^9$，$1\leq k,r\leq n$。