#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k, last = 0, q, x, y, l, r;
int a[N];
vector<int> tree[4 * N];
void build(int node, int s, int e) {
  if (s == e) {
    tree[node].push_back(a[s]);
    return;
  }
  int md = (s + e) >> 1;
  build(node << 1, s, md);
  build(node << 1 | 1, md + 1, e);
  for (auto v : tree[node << 1]) tree[node].push_back(v);
  for (auto v : tree[node << 1 | 1]) tree[node].push_back(v);
  sort(tree[node].begin(), tree[node].end());
}
int qry(int node, int s, int e, int l, int r, int target) {
  if (r < s || e < l) return 0;
  if (l <= s && e <= r) {
    int lo = 0, hi = tree[node].size() - 1;
    while (lo < hi) {
      int md = lo + (hi - lo) / 2;
      if (tree[node][md] >= target)
        hi = md;
      else
        lo = md + 1;
    }
    if (tree[node][lo] < target) return 0;
    return tree[node].size() - lo;
  }
  int md = (s + e) >> 1;
  return qry(node << 1, s, md, l, r, target) +
         qry(node << 1 | 1, md + 1, e, l, r, target);
}
vector<int> idx[N];
int main() {
  scanf("%d%d", &n, &k);
  int mx = 0;
  fill(a + 1, a + n + 1, n + 1);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    idx[x].push_back(i);
    if (idx[x].size() > k) a[idx[x][idx[x].size() - k - 1]] = i - 1;
  }
  build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &x, &y);
    l = (x + last) % n + 1;
    r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    last = qry(1, 1, n, l, r, r);
    printf("%d\n", last);
  }
}
