#include <bits/stdc++.h>
#define endl '\n'
#define MAXNUM 100003
#define MAXN 50003
#define BUCKET_SIZE 230
using namespace std;
int n, m, k;
int tr[MAXNUM];
int get(int pos)
{
if (pos <= 0)
return 0;
if (pos > 100000)
pos = 100000;
int ans = 0;
for (pos; pos >= 1; pos -= pos & -pos)
ans += tr[pos];
return ans;
}
void update(int pos, int add)
{
for (pos; pos <= 100000; pos += pos & -pos)
tr[pos] += add;
}
struct query
{
int l, r, idx;
bool operator < (const query &t) const
{
return ((l / BUCKET_SIZE < t.l / BUCKET_SIZE) || (l / BUCKET_SIZE == t.l / BUCKET_SIZE && r < t.r));
}
query() {}
query(int _l, int _r, int _idx)
{
l = _l;
r = _r;
idx = _idx;
}
};
int arr[MAXN];
query queries[MAXN];
int ans[MAXN];
int cnt;
void add_number(int num)
{
cnt += get(num - k) + get(100000) - get(num + k - 1);
update(num, 1);
}
void extract_number(int num)
{
cnt -= get(num - k) + get(100000) - get(num + k - 1);
update(num, -1);
}
void read()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 1; i <= m; i++)
{
cin >> queries[i].l >> queries[i].r;
queries[i].idx = i;
}
}
void solve()
{
sort (queries+1, queries+m+1);
int l = queries[1].l, r = queries[1].r;
for (int i = l; i <= r; i++)
add_number(arr[i]);
ans[queries[1].idx] = cnt;
for (int i = 2; i <= m; i++)
{
while (l > queries[i].l)
{
l--;
add_number(arr[l]);
}
while (l < queries[i].l)
{
extract_number(arr[l]);
l++;
}
while (r > queries[i].r)
{
extract_number(arr[r]);
r--;
}
while (r < queries[i].r)
{
r++;
add_number(arr[r]);
}
ans[queries[i].idx] = cnt;
}
for (int i = 1; i <= m; i++)
cout << ans[i] << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
solve();
}
/*
5 5 2
1 2 3 4 5
1 3
2 4
3 5
1 5
2 5
*/
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAnXG4nCiNkZWZpbmUgTUFYTlVNIDEwMDAwMwojZGVmaW5lIE1BWE4gNTAwMDMKI2RlZmluZSBCVUNLRVRfU0laRSAyMzAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG4sIG0sIGs7CmludCB0cltNQVhOVU1dOwppbnQgZ2V0KGludCBwb3MpCnsKICAgIGlmIChwb3MgPD0gMCkKICAgICAgICByZXR1cm4gMDsKICAgICAgICBpZiAocG9zID4gMTAwMDAwKQogICAgICAgICAgICBwb3MgPSAxMDAwMDA7CiAgICBpbnQgYW5zID0gMDsKICAgIGZvciAocG9zOyBwb3MgPj0gMTsgcG9zIC09IHBvcyAmIC1wb3MpCiAgICAgICAgYW5zICs9IHRyW3Bvc107CiAgICByZXR1cm4gYW5zOwp9CnZvaWQgdXBkYXRlKGludCBwb3MsIGludCBhZGQpCnsKICAgIGZvciAocG9zOyBwb3MgPD0gMTAwMDAwOyBwb3MgKz0gcG9zICYgLXBvcykKICAgICAgICB0cltwb3NdICs9IGFkZDsKfQpzdHJ1Y3QgcXVlcnkKewogICAgaW50IGwsIHIsIGlkeDsKICAgIGJvb2wgb3BlcmF0b3IgPCAoY29uc3QgcXVlcnkgJnQpIGNvbnN0CiAgICB7CiAgICAgICAgcmV0dXJuICgobCAvIEJVQ0tFVF9TSVpFIDwgdC5sIC8gQlVDS0VUX1NJWkUpIHx8IChsIC8gQlVDS0VUX1NJWkUgPT0gdC5sIC8gQlVDS0VUX1NJWkUgJiYgciA8IHQucikpOwogICAgfQogICAgcXVlcnkoKSB7fQogICAgcXVlcnkoaW50IF9sLCBpbnQgX3IsIGludCBfaWR4KQogICAgewogICAgICAgIGwgPSBfbDsKICAgICAgICByID0gX3I7CiAgICAgICAgaWR4ID0gX2lkeDsKICAgIH0KfTsKaW50IGFycltNQVhOXTsKcXVlcnkgcXVlcmllc1tNQVhOXTsKaW50IGFuc1tNQVhOXTsKaW50IGNudDsKdm9pZCBhZGRfbnVtYmVyKGludCBudW0pCnsKICAgIGNudCArPSBnZXQobnVtIC0gaykgKyBnZXQoMTAwMDAwKSAtIGdldChudW0gKyBrIC0gMSk7CiAgICB1cGRhdGUobnVtLCAxKTsKfQp2b2lkIGV4dHJhY3RfbnVtYmVyKGludCBudW0pCnsKICAgIGNudCAtPSBnZXQobnVtIC0gaykgKyBnZXQoMTAwMDAwKSAtIGdldChudW0gKyBrIC0gMSk7CiAgICB1cGRhdGUobnVtLCAtMSk7Cn0Kdm9pZCByZWFkKCkKewogICAgY2luID4+IG4gPj4gbSA+PiBrOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgICAgIGNpbiA+PiBhcnJbaV07CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBtOyBpKyspCiAgICB7CiAgICAgICAgY2luID4+IHF1ZXJpZXNbaV0ubCA+PiBxdWVyaWVzW2ldLnI7CiAgICAgICAgcXVlcmllc1tpXS5pZHggPSBpOwogICAgfQp9CnZvaWQgc29sdmUoKQp7CiAgICBzb3J0IChxdWVyaWVzKzEsIHF1ZXJpZXMrbSsxKTsKICAgIGludCBsID0gcXVlcmllc1sxXS5sLCByID0gcXVlcmllc1sxXS5yOwogICAgZm9yIChpbnQgaSA9IGw7IGkgPD0gcjsgaSsrKQogICAgICAgIGFkZF9udW1iZXIoYXJyW2ldKTsKICAgIGFuc1txdWVyaWVzWzFdLmlkeF0gPSBjbnQ7CiAgICBmb3IgKGludCBpID0gMjsgaSA8PSBtOyBpKyspCiAgICB7CiAgICAgICAgIHdoaWxlIChsID4gcXVlcmllc1tpXS5sKQogICAgICAgICB7CiAgICAgICAgICAgICBsLS07CiAgICAgICAgICAgICBhZGRfbnVtYmVyKGFycltsXSk7CiAgICAgICAgIH0KICAgICAgICAgd2hpbGUgKGwgPCBxdWVyaWVzW2ldLmwpCiAgICAgICAgIHsKICAgICAgICAgICAgIGV4dHJhY3RfbnVtYmVyKGFycltsXSk7CiAgICAgICAgICAgICBsKys7CiAgICAgICAgIH0KICAgICAgICAgd2hpbGUgKHIgPiBxdWVyaWVzW2ldLnIpCiAgICAgICAgIHsKICAgICAgICAgICAgIGV4dHJhY3RfbnVtYmVyKGFycltyXSk7CiAgICAgICAgICAgICByLS07CiAgICAgICAgIH0KICAgICAgICAgd2hpbGUgKHIgPCBxdWVyaWVzW2ldLnIpCiAgICAgICAgIHsKICAgICAgICAgICAgIHIrKzsKICAgICAgICAgICAgIGFkZF9udW1iZXIoYXJyW3JdKTsKICAgICAgICAgfQogICAgICAgICBhbnNbcXVlcmllc1tpXS5pZHhdID0gY250OwogICAgfQogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbTsgaSsrKQogICAgICAgIGNvdXQgPDwgYW5zW2ldIDw8IGVuZGw7Cn0KaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0cik7CiAgICBjb3V0LnRpZShudWxscHRyKTsKICAgIHJlYWQoKTsKICAgIHNvbHZlKCk7Cn0KLyoKNSA1IDIKMSAyIDMgNCA1CjEgMwoyIDQKMyA1CjEgNQoyIDUKKi8K