T221858 [FTLOI R1]ZQW 本着正义之名

大佬 ZQW 在 CSP-S 2021 拿了省一，他为他精妙的爆搜感到十分的自豪，于是他就很想装*。

ZQW 想考你一个数据结构题，以反衬出他的 nb。 ZQW 给你一个长度为 $n$ 的序列，他有 $m$ 个询问： `l r`：让你求 $\sum\limits_{i=l}^{r}\sum\limits_{j=i+1}^{r}(a_j\cdot[\lvert a_i-a_j\rvert \leq k])$，$k$ 为给定的常数。 你并不想被鄙视，于是你只好用有限的时间去打破他装*的幻想。

第一行三个整数 $n,m,k$ 分别表示序列的长度，询问的个数以及询问中的常数。 第二行 $n$ 个整数 $a_i$，表示序列里的元素。 后面跟着 $m$ 行 $l,r$，表示询问区间 $[l,r]$ 的答案。

共 $m$ 个数字，**用空格隔开**，输出每个询问的答案，由于答案可能有点大，所以请利用 `unsigned int` 的溢出。

样例解释： 对于 $a_1$，他和 $a_2$ 相差 $\le1$，贡献是 $1$。 对于 $a_2$，他没有贡献。 对于 $a_3$，他和 $a_4$ 相差 $\le1$，贡献是 $5$。 对于 $a_4$，他没有贡献。 一共 $1+5=6$。 --- $1\leq n,m\leq4\cdot 10^5,1\leq a_i,k\leq4\cdot10^5,1\leq l,r\leq n$ | $Subtask$ | $n\le$ | $m\le$ | $points$ | 特殊 | | :----------: | :----------: | :----------: | :----------: | :----------: | | #1 | $4$ | $1$ | $1$ | 样例 | | #2 | $10^3$ | $10^3$ | $10$ | 随机 | | #3 | $10^4$ | $10^4$ | $15$ | 随机 | | #4 | $10^5$ | $10^5$ | $19$ | 查询 $len=10^2$ | | #5 | $10^5$ | $10^5$ | $25$ | 随机 | | #6 | $4\cdot10^5$ | $4\cdot10^5$ | $30$ | 还是随机 |