#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5,M=5e5;
int n,m,k,maxn;
int a[N],b[N],c[N];
ll num[N];
ll curn;
int pre[N],pre2[N];
ll tree[N];
int l,r;
void add(int x,int y){
for(;x<=N;x+=x&-x)tree[x]+=y;
}
ll ask(int x){
ll ans=0;
for(;x;x-=x&-x)ans+=tree[x];
return ans;
}
struct query{
int l,r,id;
bool operator<(const query& q){
if(l/maxn!=q.l/maxn)return l<q.l;
return (l/maxn&1)?r<q.r:r>q.r;
}
}q[N];
void add(int x){
int down=pre[x],up=pre2[x];
curn+=ask(up)-ask(down-1);
add(c[x],1);
}
void del(int x){
add(c[x],-1);
int down=pre[x],up=pre2[x];
curn-=ask(up)-ask(down-1);
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
b[i+n]=a[i]-k;
b[i+2*n]=a[i]+k;
}
sort(b+1,b+3*n+1);
int cnt=unique(b+1,b+3*n+1)-b-1;
for(int i=1;i<=n;i++){
c[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
pre[i]=lower_bound(b+1,b+cnt+1,a[i]-k)-b;
pre2[i]=lower_bound(b+1,b+cnt+1,a[i]+k)-b;
}
for(int i=1;i<=n;i++)cout<<c[i]<<" "<<pre[i]<<" "<<pre2[i]<<endl;
for(int i=0;i<m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q,q+m);
l=1,r=0;
for(int i=0;i<m;i++){
int cl=q[i].l,cr=q[i].r,id=q[i].id;
while(l>cl)add(a[--l]);
while(r<cr)add(a[++r]);
while(l<cl)del(a[l++]);
while(r>cr)del(a[r--]);
num[id]=curn;
}
for(int i=0;i<m;i++)cout<<num[i]<<endl;
}
莫队+离散化