GZOI2017 D1T3

给定 $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,2)(2,1)$； 第二次询问好的配对有：$(1,2)(2,1),(1,3)(3,1)$； 答案 $=2\times 1+4\times 2=10$。 **【数据约束】** |数据编号|$n$|$m$|$a_i$| |:-:|:-:|:-:|:-:| |$1$|$\le300$|$\le300$|$1\le a_i\le 10^9$| |$2$|^|^|^| |$3$|$\le5000$|$\le5000$|^| |$4$|^|^|^| |$5$|$\le5 \times 10^4$|$\le5 \times 10^4$|^| |$6$|^|^|^| |$7$|^|^|^| |$8$|$\le3 \times 10^5$|$\le3 \times 10^5$|^| |$9$|^|^|^| |$10$|^|^|^| 对于 $100\%$ 的数据，$\forall 1 \le i < j \le n,a_i \ne a_j$，$1 \le l \le r \le n$。