#include <bits/stdc++.h>
using namespace std;
int const sze = 1 << 17, MOD1 = 1e9 + 9, x1 = 119, INF = -1e6, psze = 20;
struct node {
  int l, r, cnt;
  node(int l = -1, int r = -1, int cnt = 0) : l(l), r(r), cnt(cnt){};
};
node memory[sze * psze];
int my_free = 2;
int n, k;
vector<int> values;
vector<int> left_boders;
void update(int l, int r, int lb, int rb, int ind, int value) {
  if (l == lb && r == rb) {
    memory[ind].cnt = value;
    return;
  }
  int m = (lb + rb) >> 1;
  if (memory[ind].l == -1) memory[ind].l = my_free++;
  if (memory[ind].r == -1) memory[ind].r = my_free++;
  if (l <= m) update(l, min(m, r), lb, m, memory[ind].l, value);
  if (r > m) update(max(l, m + 1), r, m + 1, rb, memory[ind].r, value);
  memory[ind].cnt = memory[memory[ind].l].cnt + memory[memory[ind].r].cnt;
}
int per_update(int l, int r, int lb, int rb, int ind) {
  if (l == lb && r == rb) {
    int cur = my_free++;
    memory[cur].cnt = 1;
    return cur;
  }
  int v, cur = my_free++;
  int m = (lb + rb) >> 1;
  if (l <= m) {
    v = per_update(l, min(m, r), lb, m, memory[ind].l);
    memory[cur].l = v;
    memory[cur].r = memory[ind].r;
  }
  if (r > m) {
    v = per_update(max(l, m + 1), r, m + 1, rb, memory[ind].r);
    memory[cur].r = v;
    memory[cur].l = memory[ind].l;
  }
  memory[cur].cnt = memory[memory[cur].l].cnt + memory[memory[cur].r].cnt;
  return cur;
}
void made_persistent() {
  map<int, int> next;
  map<int, int> position;
  for (int i = n - 1; i >= 0; --i) {
    if (!position.count(values[i]))
      next[i] = -1;
    else
      next[i] = position[values[i]];
    position[values[i]] = i;
  }
  map<int, int> count;
  map<int, int> last_used;
  left_boders.push_back(my_free++);
  for (int i = 0; i < n; ++i) {
    if (count.count(values[i]))
      count[values[i]]++;
    else
      count[values[i]] = 1;
    if (count[values[i]] <= k) {
      update(i + 1, i + 1, 1, sze, left_boders[0], 1);
      last_used[values[i]] = i;
    } else
      update(i + 1, i + 1, 1, sze, left_boders[0], 0);
  }
  for (int i = 1; i < n; ++i) {
    int ind = next[last_used[values[i - 1]]];
    if (ind == -1)
      left_boders.push_back(left_boders[i - 1]);
    else {
      left_boders.push_back(
          per_update(ind + 1, ind + 1, 1, sze, left_boders[i - 1]));
      last_used[values[i - 1]] = next[last_used[values[i - 1]]];
    }
  }
}
int get(int l, int r, int lb, int rb, int ind) {
  if (l == lb && r == rb) {
    return memory[ind].cnt;
  }
  int m = (lb + rb) >> 1;
  int first = 0, second = 0;
  if (l <= m) first = get(l, min(m, r), lb, m, memory[ind].l);
  if (r > m) second = get(max(l, m + 1), r, m + 1, rb, memory[ind].r);
  return first + second;
}
signed main() {
  cin >> n >> k;
  values.resize(n);
  for (int i = 0; i < n; ++i) cin >> values[i];
  made_persistent();
  int q, last = 0;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int x, y;
    cin >> x >> y;
    int l = (x + last) % n;
    int r = (y + last) % n;
    if (l > r) swap(l, r);
    last = get(l + 1, r + 1, 1, sze, left_boders[l]);
    cout << last << '\n';
  }
  return 0;
}
