#include <bits/stdc++.h>
using namespace std;
const int N = (int)1E5 + 5;
int MOD = (int)1E9 + 7;
namespace CHT {
struct cnode {
  int s;
  int e;
  int ls;
  int rs;
  int res;
} nodes[N * 40];
void copy(int s, int d) {
  nodes[d].s = nodes[s].s;
  nodes[d].e = nodes[s].e;
  nodes[d].ls = nodes[s].ls;
  nodes[d].rs = nodes[s].rs;
  nodes[d].res = nodes[s].res;
}
int roots[N << 1];
int allo = 0;
int build(int s, int e) {
  if (s == e) {
    nodes[allo] = {s, e, -1, -1, 0};
    return allo++;
  }
  int m = s + e >> 1;
  int temp = allo++;
  int l = build(s, m);
  int r = build(m + 1, e);
  nodes[temp] = {s, e, l, r, 0};
  return temp;
}
void add(int i, int pos, int val) {
  roots[i] = allo++;
  int c1 = roots[i - 1];
  int c2 = roots[i];
  while (1) {
    copy(c1, c2);
    nodes[c2].res += val;
    if (nodes[c1].s == nodes[c1].e) break;
    int m = nodes[c1].s + nodes[c1].e >> 1;
    if (pos <= m) {
      nodes[c2].ls = allo++;
      c2 = nodes[c2].ls;
      c1 = nodes[c1].ls;
    } else {
      nodes[c2].rs = allo++;
      c2 = nodes[c2].rs;
      c1 = nodes[c1].rs;
    }
  }
}
int query(int s, int e, int r) {
  if (s == nodes[r].s && e == nodes[r].e) return nodes[r].res;
  int m = nodes[r].s + nodes[r].e >> 1;
  if (e <= m) {
    return query(s, e, nodes[r].ls);
  } else if (s >= m + 1) {
    return query(s, e, nodes[r].rs);
  } else {
    int p1 = query(s, m, nodes[r].ls);
    int p2 = query(m + 1, e, nodes[r].rs);
    return p1 + p2;
  }
}
}  // namespace CHT
using namespace CHT;
namespace fastIO {
void read(int &n) {
  char ch = ' ';
  int q = 0, w = 1;
  for (; (ch != '-') && ((ch < '0') || (ch > '9')); ch = getchar())
    ;
  if (ch == '-') w = -1, ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar()) q = q * 10 + ch - 48;
  n = q * w;
}
void read(long long &n) {
  char ch = ' ';
  long long q = 0, w = 1;
  for (; (ch != '-') && ((ch < '0') || (ch > '9')); ch = getchar())
    ;
  if (ch == '-') w = -1, ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar()) q = q * 10 + ch - 48;
  n = q * w;
}
void write(long long x) {
  if (x == 0) {
    putchar('0');
    return;
  }
  if (x < 0) x = -x, putchar('-');
  int d[21];
  d[0] = 0;
  while (x) d[++d[0]] = x % 10, x /= 10;
  for (; d[0]; d[0]--) putchar(d[d[0]] + '0');
}
};  // namespace fastIO
using namespace fastIO;
vector<int> vs[N];
void solve() {
  int n, k, temp, q;
  read(n);
  read(k);
  roots[0] = build(1, n);
  for (int i = 1; i <= n; i++) {
    read(temp);
    vs[temp].push_back(i);
    if (vs[temp].size() > k) {
      add(2 * i - 1, vs[temp][vs[temp].size() - 1 - k], -1);
    } else {
      add(2 * i - 1, 1, 0);
    }
    add(2 * i, i, 1);
  }
  read(q);
  int last = 0;
  for (int i = 0; i < q; i++) {
    int a, b;
    read(a), read(b);
    a = (last + a) % n + 1;
    b = (last + b) % n + 1;
    if (a > b) swap(a, b);
    last = query(a, b, roots[2 * b]);
    write(last);
    printf("\n");
  }
}
int main() {
  solve();
  return 0;
}
