#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
struct Node {
  int val, sum;
  Node *left, *right;
  Node(int _x = 0) : val(_x), sum(_x), left(nullptr), right(nullptr) {}
};
int n, m, k, cnt[100500], first[100500], last[100500], nxt[100500];
void update(Node *nd) {
  if (!nd) return;
  nd->sum = nd->val;
  if (nd->left) nd->sum += nd->left->sum;
  if (nd->right) nd->sum += nd->right->sum;
}
Node *build(int ql = 0, int qr = n - 1) {
  Node *root = new Node();
  if (ql < qr) {
    int qm = (ql + qr) >> 1;
    root->left = build(ql, qm);
    root->right = build(qm + 1, qr);
  }
  update(root);
  return root;
}
Node *add(Node *root, int i, int real, int ql = 0, int qr = n - 1) {
  if (ql == qr) return new Node(root->val + real);
  int qm = (ql + qr) >> 1;
  Node *res = new Node(root->val);
  if (i <= qm) {
    res->left = add(root->left, i, real, ql, qm);
    res->right = root->right;
  } else {
    res->left = root->left;
    res->right = add(root->right, i, real, qm + 1, qr);
  }
  update(res);
  return res;
}
int sum(Node *root, int l, int r, int ql = 0, int qr = n - 1) {
  if (l > r) return 0;
  if (l == ql && r == qr) return root->sum;
  int qm = (ql + qr) >> 1, ans = 0;
  if (l <= qm) ans += sum(root->left, l, min(r, qm), ql, qm);
  if (r > qm) ans += sum(root->right, max(qm + 1, l), r, qm + 1, qr);
  return ans;
}
int main() {
  scanf("%d%d", &n, &k);
  vector<Node *> v;
  v.push_back(build());
  for (int i = 0; i <= 1e5; i++) last[i] = nxt[i] = -1;
  for (int i = 0; i < n; i++) {
    int real;
    scanf("%d", &real);
    if (last[real] != -1)
      nxt[last[real]] = i;
    else
      first[real] = i;
    cnt[real]++;
    Node *tmp = add(v.back(), i, 1);
    last[real] = i;
    if (cnt[real] > k) {
      tmp = add(tmp, first[real], -1);
      first[real] = nxt[first[real]];
    }
    v.push_back(tmp);
  }
  scanf("%d", &m);
  int last_sum = 0;
  while (m--) {
    int l, r;
    scanf("%d%d", &l, &r);
    l = (l + last_sum) % n + 1;
    r = (r + last_sum) % n + 1;
    if (l > r) swap(l, r);
    last_sum = sum(v[r], l - 1, r - 1);
    printf("%d\n", last_sum);
  }
  return 0;
}
