#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 400;
int n, k, blo, bl[N];
vector<int> pos[N], v[M];
int val[N];
int query(int l, int r) {
  int ans = 0;
  for (int i = l; i <= min(bl[l] * blo, r); i++)
    if (val[i] < l) ans++;
  if (bl[l] != bl[r]) {
    for (int i = (bl[r] - 1) * blo + 1; i <= r; i++)
      if (val[i] < l) ans++;
  }
  for (int i = bl[l] + 1; i <= bl[r] - 1; i++) {
    ans += lower_bound(v[i].begin(), v[i].end(), l) - v[i].begin();
  }
  return ans;
}
int main() {
  scanf("%d %d", &n, &k);
  blo = sqrt(n);
  int maxval = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", val + i);
    bl[i] = (i - 1) / blo + 1;
    pos[val[i]].push_back(i);
    maxval = max(maxval, val[i]);
  }
  for (int i = 1; i <= maxval; i++) {
    if (pos[i].empty()) continue;
    for (int j = 0; j < pos[i].size(); j++) {
      if (j < k)
        val[pos[i][j]] = -1;
      else
        val[pos[i][j]] = pos[i][j - k];
    }
  }
  for (int i = 1; i <= n; i++) {
    v[bl[i]].push_back(val[i]);
  }
  for (int i = 1; i <= bl[n]; i++) sort(v[i].begin(), v[i].end());
  int m, l, r;
  int ans = 0;
  scanf("%d", &m);
  while (m--) {
    scanf("%d %d", &l, &r);
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    ans = query(l, r);
    printf("%d\n", ans);
  }
  return 0;
}
