#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[100005], yo[100005];
queue<int> q[100005];
vector<int> tree[500005];
void builtTree(int p, int b, int e) {
  if (b > e) return;
  if (b == e) {
    tree[p].push_back(yo[b]);
    return;
  }
  int lp = (p << 1);
  int rp = (lp | 1);
  int mid = ((b + e) >> 1);
  builtTree(lp, b, mid);
  builtTree(rp, mid + 1, e);
  int i = 0, j = 0;
  while (i < tree[lp].size() && j < tree[rp].size()) {
    if (tree[lp][i] < tree[rp][j])
      tree[p].push_back(tree[lp][i]), i++;
    else
      tree[p].push_back(tree[rp][j]), j++;
  }
  while (i < tree[lp].size()) {
    tree[p].push_back(tree[lp][i]), i++;
  }
  while (j < tree[rp].size()) {
    tree[p].push_back(tree[rp][j]), j++;
  }
}
int query(int p, int b, int e, int l, int r, int x) {
  if (b > e || l > e || r < b) return 0;
  if (l <= b && e <= r) {
    int ret = upper_bound(tree[p].begin(), tree[p].end(), x) - tree[p].begin();
    return ret;
  }
  int mid = (b + e) / 2;
  int lp = 2 * p;
  int rp = lp + 1;
  int ret1 = query(lp, b, mid, l, r, x);
  int ret2 = query(rp, mid + 1, e, l, r, x);
  return ret1 + ret2;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    q[a[i]].push(i);
    if (q[a[i]].size() == k + 1) {
      yo[i] = q[a[i]].front();
      q[a[i]].pop();
    } else
      yo[i] = -1;
  }
  builtTree(1, 1, n);
  int ans = 0;
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    l = (ans + l) % n + 1;
    r = (ans + r) % n + 1;
    if (l > r) swap(l, r);
    ans = query(1, 1, n, l, r, l - 1);
    printf("%d\n", ans);
  }
  return 0;
}
