#include <stdio.h>
#define MAXN 100000
long long p[MAXN + 1], aib[MAXN + 1], v[MAXN];
long long point[MAXN], st[MAXN], dr[MAXN], rez[MAXN];
inline long long ultb(long long x){
return x & (-x);
}
inline void add(long long p, long long val, long long n){
if(p <= n){
aib[p] += val;
add(p + ultb(p), val, n);
}
}
inline long long sum(long long p){
if(p > 0)
return aib[p] + sum(p - ultb(p));
return 0;
}
inline char better(long long a1, long long b1, long long a2, long long b2){
if(b1 > b2)
return 1;
return 0;
}
void qs(long long s, long long d){
long long i = s, j = d, pivst = st[point[(s + d) / 2]], pivdr = dr[point[(s + d) / 2]], aux;
while(i <= j){
while(better(pivst, pivdr, st[point[i]], dr[point[i]]))
i++;
while(better(st[point[j]], dr[point[j]], pivst, pivdr))
j--;
if(i <= j){
aux = point[i]; point[i] = point[j]; point[j] = aux;
i++; j--;
}
}
if(s < j)
qs(s, j);
if(i < d)
qs(i, d);
}
int main(){
FILE *in = fopen("distincte.in", "r");
long long n, k, m, i;
fscanf(in, "%lld%lld%lld", &n, &k, &m);
for(i = 0; i < n; i++)
fscanf(in, "%lld", &v[i]);
for(i = 0; i < m; i++){
fscanf(in, "%lld%lld", &st[i], &dr[i]);
point[i] = i;
}
fclose(in);
for(i = 0; i <= k; i++)
p[i] = -1;
qs(0, m - 1);
long long j = 0;
for(i = 0; i < n; i++){
if(p[v[i]] != -1)
add(p[v[i]] + 1, -v[i], n);
add(i + 1, v[i], n);
p[v[i]] = i;
while(j < m && dr[point[j]] == i + 1){
rez[point[j]] = sum(i + 1) - sum(st[point[j]] - 1);
j++;
}
}
FILE *out = fopen("distincte.out", "w");
for(i = 0; i < m; i++){
fprintf(out, "%lld\n", rez[i]);
}
fclose(out);
return 0;
}