#include <bits/stdc++.h>
using namespace std;
int lch[2000100], rch[2000100], cnt[2000100];
int tot, root[100010], a[100010], nxt[100010], sum[100010], w[100010];
int n, k, mx, T, ans;
int modify(int pre, int l, int r, int x) {
  int now = ++tot;
  if (l == r) {
    cnt[now] = cnt[pre] + 1;
    lch[now] = rch[now] = 0;
  } else {
    int mid = (l + r) >> 1;
    if (x <= mid) {
      rch[now] = rch[pre];
      lch[now] = modify(lch[pre], l, mid, x);
    } else {
      lch[now] = lch[pre];
      rch[now] = modify(rch[pre], mid + 1, r, x);
    }
    cnt[now] = cnt[lch[now]] + cnt[rch[now]];
  }
  return now;
}
int query(int root, int l, int r, int x) {
  if (l == r) return cnt[root];
  int mid = (l + r) >> 1;
  if (x <= mid)
    return cnt[rch[root]] + query(lch[root], l, mid, x);
  else
    return query(rch[root], mid + 1, r, x);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    if (w[a[i]]) nxt[w[a[i]]] = i;
    w[a[i]] = i;
    mx = max(mx, a[i]);
  }
  for (int i = 1; i <= n; i++)
    if (!nxt[i]) nxt[i] = n + 1;
  memset(w, 0, sizeof(w));
  for (int i = n; i >= 1; i--) w[a[i]] = i;
  tot = 0;
  root[0] = lch[0] = rch[0] = cnt[0] = 0;
  for (int i = 1; i <= n; i++) {
    sum[a[i]]++;
    if (sum[a[i]] > k) {
      root[i] = modify(root[i - 1], 1, n, w[a[i]]);
      w[a[i]] = nxt[w[a[i]]];
    } else
      root[i] = root[i - 1];
  }
  scanf("%d", &T);
  while (T--) {
    int l, r;
    scanf("%d%d", &l, &r);
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    ans = (r - l + 1) - query(root[r], 1, n, l);
    printf("%d\n", ans);
  }
  return 0;
}
