#include <bits/stdc++.h>

const std :: string FILENAME = "distincte";

std :: ifstream in (FILENAME + ".in");

std :: ofstream out (FILENAME + ".out");

const long long NMAX = 1e5 + 5;

long long n;

long long m;

long long k;

long long ult;

long long cnt;

long long x;

long long y;

long long v[NMAX];

long long last[NMAX];

long long arb[4 * NMAX];

long long ans[NMAX];

std :: pair <std :: pair <long long, long long>, long long> q[NMAX];

void update(long long nod, long long st, long long dr, long long val)
{
    if(st == dr)
    {
        arb[nod] += val * v[st];
    }
    else
    {
        long long mij = (st + dr) / 2;

        if(x <= mij)
        {
            update(nod * 2, st, mij, val);
        }
        else
        {
            update(nod * 2 + 1, mij + 1, dr, val);
        }

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

long long query(long long nod, long long st, long long dr)
{
    if(x <= st && y >= dr)
    {
        return arb[nod];
    }

    long long mij = (st + dr) / 2;

    if(y <= mij)
    {
        return query(nod * 2, st, mij);
    }
    if(x > mij)
    {
        return query(nod * 2 + 1, mij + 1, dr);
    }

    return query(nod * 2, st, mij) + query(nod * 2 + 1, mij + 1, dr);
}

int main()
{

    in >> n >> k >> m;

    for(long long i = 1; i <= n; i ++)
    {
        in >> v[i];
    }

    for(long long i = 1; i <= m; i ++)
    {
        in >> q[i].first.second >> q[i].first.first;

        q[i].second = i;
    }

    std :: sort(q + 1, q + m + 1);

    cnt = 1;

    for(long long i = 1; i <= n; i ++)
    {
        x = last[v[i]];

        if(x)
        {
            update(1, 1, n, - 1);
        }

        last[v[i]] = i;

        x = last[v[i]];

        update(1, 1, n, 1);

        while(q[cnt].first.first == i)
        {
            x = q[cnt].first.second;

            y = q[cnt].first.first;

            cnt ++;

            ans[q[cnt - 1].second] = query(1, 1, n);
        }
    }

    for(long long i = 1; i <= m; i ++)
    {
        out << ans[i] << '\n';
    }

    return 0;
}