#include <bits/stdc++.h>
using namespace std;
int dp[100005][20];
int nxt[100005];
int last[100005];
int a[100005];
int cnt[100005];
int n, k, q;
int root[100005];
int ID = 1;
int st[10000000];
int L[10000000];
int R[10000000];
int update(int i, int val, int id, int l = 1, int r = n) {
  if (i > r || i < l) return id;
  int idd = ID++;
  if (i == l && i == r) {
    st[idd] = val;
    return idd;
  }
  int mid = (l + r) >> 1;
  L[idd] = update(i, val, L[id], l, mid);
  R[idd] = update(i, val, R[id], mid + 1, r);
  st[idd] = st[L[idd]] + st[R[idd]];
  return idd;
}
int query(int i, int j, int id, int l = 1, int r = n) {
  if (i > r || j < l) return 0;
  if (i <= l && j >= r) return st[id];
  int mid = (l + r) >> 1;
  int c1 = query(i, j, L[id], l, mid);
  int c2 = query(i, j, R[id], mid + 1, r);
  return c1 + c2;
}
int getNext(int i, int k) {
  for (int j = 0; j < 20; j++) {
    if ((k & (1 << j)) && (dp[i][j] != -1))
      i = dp[i][j];
    else if ((k & (1 << j)) && dp[i][j] == -1) {
      i = -1;
      break;
    }
  }
  return i;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(last, -1, sizeof last);
  memset(dp, -1, sizeof dp);
  for (int i = n; i >= 1; i--) {
    nxt[i] = last[a[i]];
    last[a[i]] = i;
    dp[i][0] = nxt[i];
  }
  for (int j = 1; j <= 20; j++) {
    for (int i = 1; i <= n; i++) {
      if (dp[i][j - 1] != -1) {
        dp[i][j] = dp[dp[i][j - 1]][j - 1];
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (cnt[a[i]] == k) {
      root[1] = update(i, 0, root[1]);
    } else {
      cnt[a[i]]++;
      root[1] = update(i, 1, root[1]);
    }
  }
  for (int i = 2; i <= n; i++) {
    root[i] = root[i - 1];
    if (i != 1) {
      root[i] = update(i - 1, 0, root[i]);
      int nxxt = getNext(i - 1, k);
      if (nxxt != -1) {
        root[i] = update(nxxt, 1, root[i]);
      }
    }
  }
  scanf("%d", &q);
  int ans = 0;
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    int l = ((x + ans) % n) + 1;
    int r = ((y + ans) % n) + 1;
    if (l > r) swap(l, r);
    ans = query(l, r, root[l]);
    printf("%d\n", ans);
  }
  return 0;
}
