#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100000
using namespace std;
ifstream fin("distincte.in");
ofstream fout("distincte.out");
int a[NMAX], ST[4 * NMAX], pre[NMAX], nxt[NMAX];
vector<pair<int,int>> queries[NMAX];
void update(int node, int l, int r, int arrayIndex, int value) {
if (l == r) {
ST[node] = a[arrayIndex] = value;
return;
}
int middle = (l + r) >> 1;
if (arrayIndex <= middle) {
update(2 * node + 1, l, middle, arrayIndex, value);
} else {
update(2 * node + 2, middle + 1, r, arrayIndex, value);
}
ST[node] = ST[2 * node + 1] + ST[2 * node + 2];
}
int query(int node, int l, int r, int queryLeft, int queryRight) {
if (l >= queryLeft && queryRight >= r) {
return ST[node];
}
// if intersection is null, return -INF
if (queryLeft > r || queryRight < l) {
return 0;
}
// if intersection is partial, return the maximum of the two queries
int middle = (l + r) / 2;
return query(2 * node + 1, l, middle, queryLeft, queryRight) +
query(2 * node + 2, middle + 1, r, queryLeft, queryRight);
}
//void print(int node, int l, int r) {
// cout << node << " " << l << " " << r << " " << ST[node] << endl;
// if (l < r) {
// int middle = (l + r) / 2;
// print(2 * node + 1, l, middle);
// print(2 * node + 2, middle + 1, r);
// }
//}
int main()
{
int n, k, m;
fin >> n >> k >> m;
for (int i = 0; i < n; ++i) {
fin >> a[i];
}
vector<vector<pair<int, int>>> queries(n);
for (int i = 0; i < m; ++i){
int l, r;
fin >> l >> r;
queries[l - 1].push_back({r - 1, i});
}
vector<int> lastIndex(k, 0);
vector<int> answer(m);
for (int i = n - 1; i >= 0; --i) {
if (lastIndex[a[i]]) {
update(0, 0, n - 1, lastIndex[a[i]], 0);
}
lastIndex[a[i]] = i;
update(0, 0, n - 1, i, a[i]);
for (auto queryEnding : queries[i]) {
answer[queryEnding.second] = query(0, 0, n - 1, i, queryEnding.first);
}
}
for (int i = 0; i < m; ++i) {
fout << answer[i] << "\n";
}
return 0;
}