#include <stdio.h>
#define MAXN 100000
int p[MAXN], aib[MAXN], v[MAXN];
int point[MAXN], st[MAXN], dr[MAXN], rez[MAXN];

inline int ultb(int x){
  return x & (-x);
}

inline void add(int p, int val, int n){
  if(p <= n){
    aib[p] += val;
    add(p + ultb(p), val, n);
  }
}

inline int sum(int p){
  if(p > 0)
    return aib[p] + sum(p - ultb(p));
  return 0;
}

inline char better(int a1, int b1, int a2, int b2){
  if(b1 > b2)
    return 1;
  return 0;
}

void qs(int s, int d){
  int 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");
  int n, k, m, i;
  fscanf(in, "%d%d%d", &n, &k, &m);
  for(i = 0; i < n; i++)
    fscanf(in, "%d", &v[i]);
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &st[i], &dr[i]);
    point[i] = i;
  }
  fclose(in);
  for(i = 0; i < k; i++)
    p[i] = -1;
  qs(0, n - 1);
  int 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){
      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, "%d\n", rez[i]);
  }
  fclose(out);
  return 0;
}