#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5, K = (int)1e5;
int n, k, q, a[N];
struct node {
  int val, fr;
  node* left;
  node* right;
  node() : val(0), fr(0), left(nullptr), right(nullptr) {}
  node operator+(node o) const {
    node res;
    res.val = val + o.val;
    res.fr = fr + o.fr;
    return res;
  }
};
struct PersistentSegmentTree {
  int size, cnt;
  node* root[2 * N + 1];
  PersistentSegmentTree(int _) {
    cnt = 1, size = _;
    root[0] = new node();
    init(root[0], 1, size);
  }
  PersistentSegmentTree(int _, vector<array<int, 2>>& arr) {
    cnt = 1, size = _;
    root[0] = new node();
    init(root[0], 1, size, arr);
  }
  void init(node* crr, int lx, int rx) {
    if (lx == rx) return;
    int mid = (lx + rx) / 2;
    crr->left = new node();
    crr->right = new node();
    init(crr->left, lx, mid);
    init(crr->right, mid + 1, rx);
  }
  void init(node* crr, int lx, int rx, vector<array<int, 2>>& arr) {
    if (lx == rx) {
      crr->val = arr[lx][0];
      crr->fr = arr[lx][1];
      return;
    }
    int mid = (lx + rx) / 2;
    crr->left = new node();
    crr->right = new node();
    init(crr->left, lx, mid, arr);
    init(crr->right, mid + 1, rx, arr);
    crr->val = crr->left->val + crr->right->val;
    crr->fr = crr->left->fr + crr->right->fr;
  }
  void add(node* prev, node* crr, int id, int v, int pr, int lx, int rx) {
    if (lx == rx) {
      crr->val = prev->val + v;
      crr->fr += prev->fr + pr;
      return;
    }
    int mid = (lx + rx) / 2;
    if (id <= mid) {
      crr->right = prev->right;
      crr->left = new node();
      add(prev->left, crr->left, id, v, pr, lx, mid);
    } else {
      crr->left = prev->left;
      crr->right = new node();
      add(prev->right, crr->right, id, v, pr, mid + 1, rx);
    }
    crr->val = crr->left->val + crr->right->val;
    crr->fr = crr->left->fr + crr->right->fr;
  }
  inline void add(int id, int v, int pr) {
    root[cnt] = new node();
    add(root[cnt - 1], root[cnt], id, v, pr, 1, size);
    cnt++;
  }
  node query(node* crr, int l, int r, int lx, int rx) {
    if (l <= lx && rx <= r) return *crr;
    if (rx < l || r < lx) return node();
    int mid = (lx + rx) / 2;
    return query(crr->left, l, r, lx, mid) +
           query(crr->right, l, r, mid + 1, rx);
  }
  inline array<int, 2> query(int pref, int l, int r) {
    auto res = query(root[pref], l, r, 1, size);
    return (array<int, 2>){res.val, res.fr};
  }
};
vector<int> pos[N + 1];
int fr[N + 1], ptr[N + 1];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  for (int i = 0; i < N + 1; i++) {
    ptr[i] = k - 1;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    pos[a[i]].push_back(i + 1);
  }
  PersistentSegmentTree seg_left(n);
  vector<int> root_left, root_right;
  root_left.push_back(0);
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    if (ptr[a[i]] < (int)pos[a[i]].size()) {
      seg_left.add(pos[a[i]][ptr[a[i]]], -fr[a[i]], -1);
      cnt++;
    }
    fr[a[i]]++, ptr[a[i]]++;
    if (ptr[a[i]] < (int)pos[a[i]].size()) {
      seg_left.add(pos[a[i]][ptr[a[i]]], fr[a[i]], 1);
      cnt++;
    }
    root_left.push_back(cnt);
  }
  for (int i = 1; i <= N; i++) {
    reverse(pos[i].begin(), pos[i].end());
    ptr[i] = k - 1;
  }
  cnt = 0;
  vector<array<int, 2>> init(n + 1, {0, 0});
  for (int i = 1; i <= N; i++) {
    if (fr[i] >= k) {
      init[pos[i][k - 1]][0] += fr[i];
      init[pos[i][k - 1]][1]++;
    }
  }
  PersistentSegmentTree seg_right(n, init);
  root_right.push_back(0);
  for (int i = n - 1; i >= 0; i--) {
    if (ptr[a[i]] < (int)pos[a[i]].size()) {
      seg_right.add(pos[a[i]][ptr[a[i]]], -fr[a[i]], -1);
      cnt++;
    }
    fr[a[i]]--, ptr[a[i]]++;
    if (ptr[a[i]] < (int)pos[a[i]].size()) {
      seg_right.add(pos[a[i]][ptr[a[i]]], fr[a[i]], 1);
      cnt++;
    }
    root_right.push_back(cnt);
  }
  reverse(root_right.begin(), root_right.end());
  int ans = 0;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l = (l + ans) % n + 1;
    r = (r + ans) % n + 1;
    if (l > r) swap(l, r);
    l--;
    array<int, 2> l_val = seg_left.query(root_left[l], 1, r);
    array<int, 2> r_val = seg_right.query(root_right[r], l + 1, n);
    int res = r_val[0] - l_val[0] - k * r_val[1];
    l++;
    ans = r - l + 1 - res;
    cout << ans << '\n';
  }
  return 0;
}
