參考code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);

const int e9 = 1e9;
const int e6 = 1e6;

int dp[e6][20];

int main() {

    fast

    int n, q, k; cin >> n >> q >> k;

    for(int i = 0;i < n;i++) {
        dp[i][0] = e9;
    }

    vector<int> v(n);

    for(int i = 0;i < n;i++) {
        cin >> v[i];
    }

    vector<int> cnt(n+1, 0);
    int l = 0, r = 0, now = 0;

    while(r < n && now < k) {
        if(!cnt[v[r]]) ++now;
        ++cnt[v[r]];
        ++r;
    }
    --r;

    while(r < n) {
        while(now >= k) {
            if(now == k && cnt[v[l]] == 1) break;
            --cnt[v[l]];
            if(!cnt[v[l]]) --now;
            ++l;
        }

        dp[l][0] = min(dp[l][0], r+1);
        ++r;
        if(r >= n) break;
        if(!cnt[v[r]]) ++now;
        ++cnt[v[r]];
    }

    for(int i = n-2;i >= 0;--i) {
        dp[i][0] = min(dp[i][0], dp[i+1][0]);
    }

    for(int j = 1;j < 20;++j) {
        for(int i = 0;i < n;++i) {
            if(dp[i][j-1] >= n) {
                dp[i][j] = e9;
                continue;
            }
            dp[i][j] = dp[dp[i][j-1]][j-1];
        }
    }

    while(q--) {
        cin >> l >> r;
        --l;
        int ans = 0;
        for(int i = 19;i >= 0;--i) {
            if(l < n && dp[l][i] <= r) {
                ans += 1<<i;
                l = dp[l][i];
            }
        }

        cout << ans << '\n';
    }


    return 0;
}