permutation

给定一个 $1\sim n$ 的排列 $p_i$，定义一个区间的权值 $f(l,r)$ 如下：

• 设 $w=\min\limits_{i=l}^{r} p_i$，$f(l,r)$ 为最小的 $w'$ 使得 $w'>w$ 且 $w'$ 不等于 $[l,r]$ 中任何一个 $p_i$。

$q$ 次询问，每次询问给出 $l',r'$，输出 $\sum\limits_{l'\leq l\leq r\leq r'} f(l,r)$。

输入格式

本题单个测试点有多组测试数据，第一行两个整数 $id,T$，表示测试点编号和数据组数。样例的测试点编号为 $0$。

对于每组数据，第一行两个整数 $n,q$。

接下来一行 $n$ 个整数，表示排列 $p$。

接下来 $q$ 行，每行两个整数 $l',r'$，表示询问的两个端点。

输出格式

对于每个询问，输出单独一行表示这个询问的答案。

提示

对于 $100\%$ 的数据，$1\leq T\leq 3,1\leq n,q\leq 2\times 10^5$，保证 $p$ 是排列，$1\leq l'\leq r'\leq n$。

本题总共有 $100$ 个测试点，通过每个测试点可以获得 $1$ 分。

对于测试点 $1$，是样例。

对于测试点 $2\sim 10$， 满足 $n,q\leq 10^2$。

对于测试点 $11\sim 25$， 满足 $n,q\leq 10^3$。

对于测试点 $26\sim 40$，满足 $n\leq 5\times 10^4,q=1$。

对于测试点 $41\sim 55$，满足 $n,q\leq 5\times 10^4$，排列 $p$ 随机生成。

对于测试点 $56\sim 65$，满足 $n,q\leq 5\times 10^4$。

对于测试点 $66\sim 80$，满足 $q=1$。

对于测试点 $81\sim 90$，满足排列 $p$ 随机生成。

对于测试点 $91\sim 100$，无特殊限制。