#include <bits/stdc++.h>

using namespace std;

ifstream fin("distincte.in");
ofstream fout("distincte.out");

struct Int{
    int x, y;
    bool operator<(const Int& other) const{
        if(y == other.y){
            return x > other.x;
        }
        return y > other.y;
    }
} A[100005];

int v[100005], AIB[100005], N;
queue<int> q[100005];

void update(int poz, int val){
    for(int i = poz; i <= N; i += (i & -i)){
        AIB[i] += val;
    }
}

int query(int poz){
    int s = 0;
    for(int i = poz; i > 0; i -= (i & -i)){
        s += AIB[i];
    }
    return s;
}

int main()
{
    int M, K;
    fin >> N >> K >> M;
    for(int i = 1; i <= N; ++ i){
        fin >> v[i];
    }
    for(int i = 1; i <= M; ++ i){
        fin >> A[i].x >> A[i].y;
    }
    sort(A + 1, A + M + 1);
    int st = N, dr = N;
    for(int i = 1; i <= M; ++ i){
        while(st >= A[i].x){
            q[v[st]].push(st);
            if(q[v[st]].size() == 1){
                update(st, v[st]);
            }
            -- st;
        }
        while(dr > A[i].y){
            update(dr, - v[dr]);
            q[v[dr]].pop();
            if(q[v[dr]].size() > 0){
                update(dr, v[dr]);
            }
            -- dr;
        }
        fout << query(N) << '\n';

    }
    return 0;
}