#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e9 + 7;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int n, k;
queue<int> q[N];
vector<int> f[N];
void add(int x, int v) {
  while (x <= n) {
    f[x].push_back(v);
    x += x & -x;
  }
}
int find(int x, int v) {
  int s = 0;
  while (x) {
    s += f[x].end() - lower_bound(f[x].begin(), f[x].end(), v);
    x -= x & -x;
  }
  return s;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  int x;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    q[x].push(i);
    if (q[x].size() > k) {
      add(i, q[x].front());
      q[x].pop();
    }
  }
  for (int i = 1; i <= n; i++) {
    sort(f[i].begin(), f[i].end());
  }
  int q;
  cin >> q;
  int l, r, ans = 0;
  while (q--) {
    cin >> l >> r;
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    ans = (r - l + 1) - find(r, l);
    printf("%d\n", ans);
  }
}
