#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> pos[N];
int mp[N];
int n, k, q;
struct wavelet {
  int lo, hi;
  wavelet *left, *right;
  vector<int> amt;
  wavelet(int lo, int hi) : lo(lo), hi(hi), left(0), right(0) {}
  void build(int *b, int *e) {
    if (lo == hi) return;
    amt.reserve(e - b + 1);
    amt.push_back(0);
    int m = (lo + hi) / 2;
    for (auto it = b; it != e; it++) amt.push_back(amt.back() + (*it <= m));
    auto p = stable_partition(b, e, [=](int x) { return x <= m; });
    (left = new wavelet(lo, m))->build(b, p);
    (right = new wavelet(m + 1, hi))->build(p, e);
  }
  int qkth(int l, int r, int k) {
    if (r < l) return 0;
    if (lo == hi) return lo;
    if (k <= amt[r] - amt[l - 1]) return left->qkth(amt[l - 1] + 1, amt[r], k);
    return right->qkth(l - amt[l - 1], r - amt[r], k - amt[r] + amt[l - 1]);
  }
  int qleq(int l, int r, int mx) {
    if (r < l || mx < lo) return 0;
    if (hi <= mx) return r - l + 1;
    return left->qleq(amt[l - 1] + 1, amt[r], mx) +
           right->qleq(l - amt[l - 1], r - amt[r], mx);
  }
};
wavelet *tree;
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (auto i = (1) - ((1) > (n + 1)); i != n + 1 - ((1) > (n + 1));
       i += 1 - 2 * ((1) > (n + 1))) {
    int x;
    cin >> x;
    mp[i] = n + 1;
    pos[x].push_back(i);
    if ((int)pos[x].size() > k) mp[pos[x][(int)pos[x].size() - k - 1]] = i;
  }
  0 << 0;
  (tree = new wavelet(1, N))->build(mp + 1, mp + n + 1);
  cin >> q;
  int last = 0;
  while (q--) {
    int x, y;
    cin >> x >> y;
    int l = (x + last) % n + 1;
    int r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    0 << 0 << 0 << 0;
    last = r - l + 1 - tree->qleq(l, r, r);
    cout << last << '\n';
  }
  return 0;
}
