#include <bits/stdc++.h>
using namespace std;
const int inf = 1e5 + 9, lg = 18, sz = lg * inf << 2;
int n, k, m, cnt = 1;
int a[inf], root[inf], tree[sz], le[sz], ri[sz];
queue<int> q[inf];
void build(int node, int l, int r) {
  if (l == r) return;
  le[node] = cnt++;
  ri[node] = cnt++;
  build(le[node], l, (l + r) / 2);
  build(ri[node], (l + r) / 2 + 1, r);
}
void upgrade(int pre, int cur, int l, int r, int idx, int val) {
  if (l == r) return void(tree[cur] += val + tree[pre]);
  le[cur] = le[pre], ri[cur] = ri[pre];
  if (idx <= (l + r) / 2)
    le[cur] = cnt++, upgrade(le[pre], le[cur], l, (l + r) / 2, idx, val);
  else
    ri[cur] = cnt++, upgrade(ri[pre], ri[cur], (l + r) / 2 + 1, r, idx, val);
  tree[cur] = tree[le[cur]] + tree[ri[cur]];
}
int query(int node, int l, int r, int x, int y) {
  if (l > r || r < x || l > y) return 0;
  if (l >= x && r <= y) return tree[node];
  return query(le[node], l, (l + r) / 2, x, y) +
         query(ri[node], (l + r) / 2 + 1, r, x, y);
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  root[0] = cnt++;
  build(root[0], 1, n);
  int last_root = root[0];
  for (int i = 1; i <= n; i++) {
    int val = a[i], temp_root;
    if (q[val].size() == k) {
      temp_root = cnt++;
      upgrade(last_root, temp_root, 1, n, q[val].front(), -1);
      last_root = temp_root;
      q[val].pop();
    }
    q[val].push(i);
    root[i] = cnt++;
    upgrade(last_root, root[i], 1, n, i, 1);
    last_root = root[i];
  }
  cin >> m;
  int last_ans = 0;
  while (m--) {
    int l, r;
    cin >> l >> r;
    l = (l + last_ans) % n + 1;
    r = (r + last_ans) % n + 1;
    if (l > r) swap(l, r);
    last_ans = query(root[r], 1, n, l, r);
    cout << last_ans << endl;
  }
}
