#include <bits/stdc++.h>
using namespace std;
struct node {
  node *l, *r;
  int val;
};
queue<int> dl[100005];
node t[4000005];
node *pt = t, *roots[100005];
int a[100005];
void update(node *&root, int l, int r, int idx, int val) {
  if (l > r || l > idx || r < idx) return;
  node *u = root;
  root = pt++;
  if (u) {
    *root = *u;
  }
  if (l == r) {
    root->val += val;
    return;
  }
  int m = (l + r) / 2;
  if (idx <= m) {
    update(root->l, l, m, idx, val);
  } else {
    update(root->r, m + 1, r, idx, val);
  }
  root->val = (root->l ? root->l->val : 0) + (root->r ? root->r->val : 0);
}
int query(node *root, int l, int r, int s, int e) {
  if (!root) return 0;
  if (l > r || l > e || r < s) return 0;
  if (l >= s && r <= e) return root->val;
  int m = (l + r) / 2;
  int q1 = query(root->l, l, m, s, e), q2 = query(root->r, m + 1, r, s, e);
  return q1 + q2;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    roots[i] = roots[i - 1];
    dl[a[i]].push(i);
    if (dl[a[i]].size() > k) {
      int o = dl[a[i]].front();
      dl[a[i]].pop();
      update(roots[i], 1, n, o, -1);
    }
    update(roots[i], 1, n, i, 1);
  }
  int q;
  cin >> q;
  int last = 0;
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    l = (l + last) % n + 1;
    r = (r + last) % n + 1;
    if (l > r) {
      swap(l, r);
    }
    last = query(roots[r], 1, n, l, r);
    cout << last << endl;
  }
  return 0;
}
