#include <iostream>
#include <vector>
#include <assert.h>

struct BIT {
  const int M = 666013;
  int N;
  std::vector<int> tree;
  BIT(int N_) : N(N_), tree(N_ + 1) {}
  void update(int pos, int delta) {
    for (int i = ++pos; i <= N; i += (i & (-i))) {
      tree[i] += delta;
      if (tree[i] >= M) {
        tree[i] -= M;
      }
      if (tree[i] < 0) {
        tree[i] += M;
      }
    }
  }
  int query(int pos) {
    int answer = 0;
    for (int i = ++pos; i > 0; i -= (i & (-i))) {
      answer += tree[i];
      if (answer >= M) {
        answer -= M;
      }
    }
    return answer;
  }
  int query(int a, int b) {
    return query(b) - query(a - 1);
  }
};

int main() {
  assert(freopen("distincte.in", "r", stdin));
  assert(freopen("distincte.out", "w", stdout));

  int N, M, Q;
  std::cin >> N >> M >> Q;
  std::vector<int> V(N);
  for (int &x : V) {
    std::cin >> x;
    x--;
  }
  std::vector<std::vector<std::pair<int, int>>> queries(N);
  for (int i = 0; i < Q; i++) {
    int a, b;
    std::cin >> a >> b;
    a--;
    b--;
    queries[b].emplace_back(a, i);
  }
  std::vector<int> lastSeen(M, -1);
  std::vector<int> answer(Q);
  BIT FT(N);
  for (int r = 0; r < N; r++) {
    if (lastSeen[V[r]] != -1) {
      FT.update(lastSeen[V[r]], -V[r] - 1);
    }
    FT.update(r, V[r] + 1);
    lastSeen[V[r]] = r;
    for (std::pair<int, int> &query : queries[r]) {
      answer[query.second] = FT.query(query.first, r);
    }
  }
  for (const int &x : answer) {
    std::cout << x << "\n";
  }
  return 0;
}