#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], now[N], nxt[N], pre[N], nxtk[N], ans = 0;
vector<int> vc[N << 2];
void build(int rt, int l, int r) {
  if (l == r) {
    vc[rt].push_back(nxtk[l]);
    return;
  }
  for (int i = l; i <= r; i++) vc[rt].push_back(nxtk[i]);
  sort(vc[rt].begin(), vc[rt].end());
  int m = (l + r) >> 1;
  build(rt << 1, l, m);
  build(rt << 1 | 1, m + 1, r);
}
void query(int L, int R, int rt, int l, int r) {
  if (L <= l && r <= R) {
    int T = upper_bound(vc[rt].begin(), vc[rt].end(), R) - vc[rt].begin();
    ans -= T;
    return;
  }
  int m = (l + r) >> 1;
  if (L <= m) query(L, R, rt << 1, l, m);
  if (R > m) query(L, R, rt << 1 | 1, m + 1, r);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k, q, l, r;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i < N; i++) now[i] = n + 1;
  nxt[n + 1] = n + 1;
  for (int i = n; i >= 1; i--) {
    nxt[i] = now[a[i]];
    pre[now[a[i]]] = i;
    now[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (i == now[a[i]]) {
      int t = i, cnt = 0;
      while (t != n + 1 && cnt < k) {
        t = nxt[t];
        cnt++;
      }
      nxtk[i] = t;
    } else {
      nxtk[i] = nxt[nxtk[pre[i]]];
    }
  }
  cout << endl;
  build(1, 1, n);
  cin >> q;
  while (q--) {
    cin >> l >> r;
    l += ans;
    r += ans;
    l = l % n + 1;
    r = r % n + 1;
    if (l > r) swap(l, r);
    ans = r - l + 1;
    query(l, r, 1, 1, n);
    cout << ans << endl;
  }
  return 0;
}
