SP11676 CPAIR2 - Counting diff-pairs

给定长度为 $n$ 的序列 $a$ 和一个整数 $k$，以及 $m$ 次询问。 每次询问给出 $l,r$，求满足 $l\leq i

第一行给定三个整数 $n,m,k$。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。 接下来 $m$ 行，每行两个整数 $l,r$ 表示一次询问。

共 $m$ 行，第 $i$ 行给出第 $i$ 次询问的答案。

对于 $100\%$ 的数据，满足 $1\leq n,m\leq5\times10^4,1\leq a_i\leq 10^5$。