struct segment_tree{
    vector < int > t;
    int siz;
    void build(int siz1) {
        siz = siz1;
        t.resize(4 * siz);
        return ;
    }
    int reask(int v, int l, int r, int tl, int tr) {
        if (l == tl && r == tr) {
            return t[v];
        }
        int m = (l + r) / 2;
        int ret = 0;
        if (tl <= m) ret += reask(v * 2 + 1, l, m, tl, min(m, tr));
        if (tr >= m + 1) ret += reask(v * 2 + 2, m + 1, r, max(m + 1, tl), tr);
        return ret;
    }
    int ask(int l, int r) {
        return reask(0, 0, siz - 1, l, r);
    }
    void reupd(int v, int l, int r, int pos, int val) {
        if (l == r) {
            t[v] = val;
            return ;
        }
        int m = (l + r) / 2;
        if (pos <= m) reupd(v * 2 + 1, l, m, pos, val);
        else reupd(v * 2 + 2, m + 1, r, pos, val);
        t[v] = t[v * 2 + 1] + t[v * 2 + 2];
    }
    void upd(int pos, int val) {
        reupd(0, 0, siz - 1, pos, val);
    }

};
struct type {
    bool isupd;
    int x, ind;
    int priority;
    /// сколько чисел на отрезке больше, чем x?
    /// or {a[i], i} = {x, ind}
};
int n, q, k;
vector < int > nxt, lft;
vector < int > a;
void precalc() {
    nxt.resize(n);
    lft.resize(n);
    vector < pair < int, int > > buba;
    buba.resize(n);
    fori(n) buba[i] = {a[i], i};
    sort(all(buba));
    int r = n - 1;
    set < int > s;
    for (int i = n - 1; i >= 0; i--) {
        while (true) {
            if (buba[r].ff - buba[i].ff <= k) break;
            s.erase(buba[r].ss);
            r--;
        }
        auto c = s.upper_bound(buba[i].ss);
        if (c != s.end()) {
            nxt[buba[i].ss] = *c;
        } else {
            nxt[buba[i].ss] = n;
        }
        if (c != s.begin()) {
            c--;
            lft[buba[i].ss] = *c;
        } else {
            lft[buba[i].ss] = -1;
        }
        s.insert(buba[i].ss);
    }
}
int main() {
    srand(time(NULL));
    cin >> n >> q >> k;
    a.resize(n);
    nxt.resize(n);
    lft.resize(n);
    fori(n) cin >> a[i];
    vector < vector < int > > jmp;
    jmp.resize(n);
    precalc();
    fori(n) {
        if (lft[i] == -1) continue;
        jmp[lft[i]].pb(i);
    }
    vector < vector < pair < int, int > > > ask; //ask[l] = {{r, ind}, {r, ind}...}
    ask.resize(n);
    fori(q) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        ask[l].pb({r, i});
    }
    vector < int > ans;
    ans.resize(q);
    int cur = 0;
    vector < vector < type > > another_ask;
    fori(n) cout << nxt[i] << " ";
    cout << "\n";
    for (int i = n - 1; i >= 0; i--) {
        for (auto to: jmp[i]) {
            cout << "upd " << nxt[to] << "\n";
            nxt[to] = -1;
        }
        for (int j = 0; j < ask[i].size(); j++) {
            int r = ask[i][j].ff;
            cur = 0;
            for (int z = i; z <= r; z++) {
                if (nxt[z] > r) cur++;
            }
            cout << "ask " << i << " " << r << "more than " << r << " = " << cur << "\n";
            ans[ask[i][j].ss] = cur;
        }
    }
    fori(ans.size()) cout << ans[i] << " ";
}