#include <bits/stdc++.h>
using namespace std;
const pair<int, int> queen[8] = {pair<int, int>(-1, 0), pair<int, int>(-1, 1),
                                 pair<int, int>(0, 1),  pair<int, int>(1, 1),
                                 pair<int, int>(1, 0),  pair<int, int>(1, -1),
                                 pair<int, int>(0, -1), pair<int, int>(-1, -1)};
const int maxN = 1e5 + 11;
typedef int i_N[maxN];
int N, K, Q, last;
deque<int> pos[maxN];
i_N A;
struct node {
  int val, L, R;
  node *left, *right;
  node() {
    val = L = R = 0;
    left = right = NULL;
  }
  node(int L, int R) : L(L), R(R) {
    val = 0;
    left = right = NULL;
  }
  node(node *x) { *this = *x; }
} * IT[maxN];
pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
  return pair<int, int>(a.first + b.first, a.second + b.second);
}
node *update(node *root, const int l, const int r, const int i, const int v) {
  if (i < l || i > r) return NULL;
  node *res = root == NULL ? new node(l, r) : new node(root);
  res->val += v;
  if (l == r) return res;
  const int mid = (l + r) / 2;
  if (i <= mid)
    res->left = update(res->left, l, mid, i, v);
  else
    res->right = update(res->right, mid + 1, r, i, v);
  return res;
}
int get_IT(node *root, const int i, const int j) {
  if (root == NULL) return 0;
  const int l = root->L, r = root->R;
  if (j < l || i > r) return 0;
  if (i <= l && j >= r) return root->val;
  return get_IT(root->left, i, j) + get_IT(root->right, i, j);
}
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
  for (int i = 1; i <= N; i++) {
    pos[A[i]].push_back(i);
    IT[i] = update(IT[i - 1], 1, N, i, 1);
    if ((int)pos[A[i]].size() > K) {
      IT[i] = update(IT[i], 1, N, pos[A[i]].front(), -1);
      pos[A[i]].pop_front();
    }
  }
  scanf("%d", &Q);
  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);
    printf("%d\n", last = get_IT(IT[r], l, r));
  }
}
