{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"LQ学长给你一个整数序列a1,a2,…,an和m个任务。对于每个任务,您需要在给定的时间间隔内回答“友好对”的数量。\n友好对:对于两个整数ai和aj,如果i\u003cj且ai−aj的绝对值不大于给定的常数整数K,则(i,j)称为“友好对”。在区间[L,R]中的友好对(i,j)应满足L≤i\u003cj≤R。"}},{"title":"Input","value":{"format":"MD","content":"第一行包含3个整数n(1≤n≤27000)、m(1≤m≤27000)和K(1≤K≤109),表示序列a中的整数个数、任务数和给定的常量整数。\n\n第二行包含n个非负整数,代表序列a中的整数。序列a的每个整数不超过109。\n\n接下来是m行,每行包含两个整数L,R(1≤L≤R≤n)。意思是询问间隔[L,R]中“友好对”的数量"}},{"title":"Output","value":{"format":"MD","content":"对于每个任务,您需要输出一行,其中只有一个整数,表示查询间隔中“友好对”的数量。"}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e7 5 3\n2 5 7 5 1 5 6\n6 6\n1 3\n4 6\n2 4\n3 4\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003e0\n2\n1\n3\n1\u003c/pre\u003e"}}]}