给定 $n$ 个数 $a_1,\cdots,a_n$。
对于一组配对 $(x,y)$，若对于所有的 $i=1,2,\cdots,n$，满足 $|a_x-a_y|\le|a_x-a_i|(i\not=x)$，则称 $(x,y)$ 为一组好的配对（$|x|$ 表示 $x$ 的绝对值）。
给出若干询问，每次询问区间 $[l,r]$ 中含有多少组好的配对。
即，取 $x,y$（$l\le x,y\le r$ 且 $x\not=y$），问有多少组 $(x,y)$ 是好的配对。
输入格式
第一行两个正整数 $n,m$。
第二行 $n$ 个数 $a_1,\cdots,a_n$。
接下来 $m$ 行，每行给出两个数 $l,r$。
输出格式
$Ans_i$ 表示第 $i$ 次询问的答案，输出 $\sum_{i=1}^m\limits Ans_i\times i$ 即可。
样例数据
样例 1 输入
3 2 2 1 3 1 2 1 3
样例 1 输出
10
子任务
对于 $20\%$ 的数据，$n,m \leq 300$
对于 $40\%$ 的数据，$n,m \leq 5\,000$
对于 $70\%$ 的数据，$n,m \leq 50\,000$
对于 $100\%$ 的数据，$1 \leq n,m \leq 3 \times 10^5$，$1 \leq a_i \leq 10^9$，$1 \leq l \leq r \leq n$，$a_i \ne a_j$ 对所有 $i \ne j$