#include <cstdio>
#include <ctype.h>
#include <algorithm>
#include <queue>
#define MAXN 100000
#define BUF_SIZE (1<<17)
#define MOD 666013

using namespace std;
queue <int> lista[MAXN];

char buf[BUF_SIZE];
int poz, sol, n, m, l1, l2, r, pos = BUF_SIZE, oaie, v[MAXN+1], aint[4 * MAXN + 1];

FILE *fin, *fout;

struct aa{
    int l1, l2, ans, ind;
}q[MAXN+1];

inline char getChar();
inline int getInt();

bool cmp(const aa &v1, const aa &v2){
    return (v1.l1 < v2.l1);
}

bool cmp2(const aa &v1, const aa &v2){
    return (v1.ind < v2.ind);
}

inline void adauga(int x, int y){
    lista[x].push(y);
}

void update(int st, int dr, int nod)
{
    if(st == dr){
        aint[nod] = oaie;
        return;
    }
    int m = (st+dr)/2;
    if(poz <= m) update(st, m, nod*2);
    if(poz > m) update(m+1, dr, nod*2+1);

    aint[nod] = aint[nod*2] + aint[nod*2+1];
}

void query(int st, int dr, int nod)
{
    if(l1 <= st && dr <= l2){
        sol += aint[nod];
        return;
    }
    int m = (st+dr)/2;
    if(l1 <= m) query(st, m, nod*2);
    if(l2 > m) query(m+1, dr, nod*2+1);
}

int main()
{
    fin = fopen("distincte.in", "r");
    fout = fopen("distincte.out", "w");

    int i, x, j, k;

    n = getInt();
    k = getInt();
    m = getInt();

    for(i=1; i<=n; ++i)
    {
        x = getInt();
        if(lista[x].empty()){
            poz = i;
            oaie = v[i] = x;
            update(1, n, 1);
        }
        adauga(x, i);
    }

    for(i=1; i<=m; ++i){
        q[i].l1 = getInt();
        q[i].l2 = getInt();
        q[i].ind = i;
    }

    sort(q+1, q+m+1, cmp);

    j=1;
    for(i=1; i<=m; ++i)
    {
        while(j<=n && j < q[i].l1){
            if(v[j])
            {
                lista[v[j]].pop();
                oaie = 0;
                poz = j;
                update(1, n, 1);

                oaie = v[j];
                poz = lista[v[j]].front();
                update(1, n, 1);
                v[poz] = v[j];
            }
            j++;
        }
        l1 = q[i].l1;
        l2 = q[i].l2;
        sol = 0;
        query(1, n, 1);

        q[i].ans = sol;
    }

    sort(q+1, q+m+1, cmp2);

    for(i=1; i<=m; ++i)
        fprintf(fout, "%d\n", q[i].ans);

    return 0;
}

inline char getChar()
{
    if(pos == BUF_SIZE) pos = 0, fread(buf, 1, BUF_SIZE, fin);
    return buf[pos++];
}

inline int getInt()
{
    int nr = 0;
    char c;

    c = getChar();
    while(!isdigit(c)) c = getChar();
    while(isdigit(c))
    {
        nr = nr*10 + c-'0';
        c = getChar();
    }

    return nr;
}