void solve() {
    int n, x, q;
    cin >> n >> x >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= i;
    }
    map<int, int> f;
    for (int i = 0; i < x; i++) {
        f[a[i]]++;
    }
    multiset<int, greater<int>> mt;
    for (auto it : f) {
        mt.insert(it.second);
    }
    vector<int> ans(n - x + 1);
    ans[0] = x - *mt.begin();
    for (int i = x; i < n; i++) {
        int cur = i;
        int beg = i - x;
        mt.erase(mt.find(f[a[beg]]));
        f[a[beg]]--;
        mt.insert(f[a[beg]]);
        mt.erase(mt.find(f[a[cur]]));
        f[a[cur]]++;
        mt.insert(f[a[cur]]);
        ans[beg] = x - *mt.begin();
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ans[l - 1] << "\n";
    }
}

    multiset<int, greater<int>> mt;
    for(int i = 1; i <= n; i++) {
        mt.insert(0);
    }