#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, k, q, a[maxn];
typedef struct node* pnode;
struct node {
  int sum;
  pnode L, R;
  node() {
    sum = 0;
    L = R = NULL;
  }
};
int sum(pnode idx) {
  if (!idx) return 0;
  return idx->sum;
}
pnode build(int i, int j) {
  pnode idx = new node();
  if (i == j) return idx;
  int mid = (i + j) >> 1;
  idx->L = build(i, mid);
  idx->R = build(mid + 1, j);
  return idx;
}
pnode update(pnode cur, int i, int j, int pos, int val) {
  pnode idx = new node();
  idx->L = cur->L;
  idx->R = cur->R;
  idx->sum = cur->sum;
  if (i == j) {
    idx->sum += val;
    return idx;
  }
  int mid = (i + j) >> 1;
  if (pos <= mid)
    idx->L = update(idx->L, i, mid, pos, val);
  else
    idx->R = update(idx->R, mid + 1, j, pos, val);
  idx->sum = sum(idx->L) + sum(idx->R);
  return idx;
}
int query(pnode l, pnode r, int i, int j, int ini, int fim) {
  if (i > j || j < ini || fim < i) return 0;
  if (ini <= i && j <= fim) return r->sum - l->sum;
  int mid = (i + j) >> 1;
  return query(l->L, r->L, i, mid, ini, fim) +
         query(l->R, r->R, mid + 1, j, ini, fim);
}
deque<int> pos[maxn];
pnode root[maxn];
void precompute() {
  root[0] = build(1, n);
  for (int i = 1; i <= n; ++i) {
    pos[a[i]].push_back(i);
    root[i] = update(root[i - 1], 1, n, i, 0);
    if (pos[a[i]].size() > k) {
      int p = pos[a[i]].front();
      pos[a[i]].pop_front();
      root[i] = update(root[i], 1, n, p, +1);
    }
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  precompute();
  scanf("%d", &q);
  int last = 0;
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    l = (l + last) % n + 1;
    r = (r + last) % n + 1;
    if (l > r) swap(l, r);
    int ans = (r - l + 1) - query(root[l - 1], root[r], 1, n, l, r);
    printf("%d\n", ans);
    last = ans;
  }
  return 0;
}
