#include <stdio.h>
#define NMAX 100100
#define TMAX (1<<17)

int N, K, M, V[NMAX], S[NMAX], A[NMAX], Cnt[NMAX], Last[NMAX], T[2*TMAX], X, Y, Sum;

void update(int p1, int p2, int nod, int sum)
{
        int mij  = (p1+p2)/2;

        if (X <= p1 && p2 <= Y)
        {
                T[nod] += sum;
                return;
        }
        if ( (p1 <= X && X <= p2) || (p1 <= Y && Y <= p2) )
        {
                update(p1, mij, 2*nod, sum);
                update(mij+1, p2, 2*nod+1, sum);
        }
}

void query(int p1, int p2, int nod)
{
        int mij  = (p1+p2)/2;

        if (X <= p1 && p2 <= Y)
        {
                Sum += T[nod];
                return;
        }
        if ( (p1 <= X && X <= p2) || (p1 <= Y && Y <= p2) )
        {
                query(p1, mij, 2*nod);
                query(mij+1, p2, 2*nod+1);
        }
}

int main()
{
        int i, j, k , sum = 0;

        freopen("distincte.in", "r", stdin);
        scanf("%d %d %d", &N, &K, &M);

        for (i = 1; i <= N; ++i)
        {
                scanf("%d", V+i);
                S[i] = S[i-1]+V[i];
                Cnt[ V[i] ]++;
                A[i] = A[i-1]+V[i]*(Cnt[ V[i] ]>1);
                if (Last[ V[i] ] > 0)
                {
                        X = Last[ V[i] ]+1; Y = i-1;
                        if (X <= Y) update(0, TMAX-1, 1, V[i]);
                }
                Last[ V[i] ] = i;
        }

        if (N*N*M <= 50000000)
        {
            freopen("distincte.out", "w", stdout);
            while (M--)
            {
                    sum = 0;
                    scanf("%d %d", &i, &j);
                    for (k = 1; k <= K; k++) Cnt[k] = 0;
                    for (k = i; k <= j; k++) Cnt[ V[k] ] = 1;
                    for (k = 1; k <= K; k++) sum += (k*Cnt[k]);
                    printf("%d\n", sum);
            }
            return 0;
        }

        freopen("distincte.out", "w", stdout);
        while (M--)
        {
                scanf("%d %d", &j, &i);
                Sum = 0;
                X = j; Y = i;
                query(0, TMAX-1, 1);
                printf("%d\n", S[i]-S[j-1]-A[i+1]+A[j]+Sum);
        }

        return 0;
        
}