#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

constexpr size_t LIM = 100005;

struct Query {
    int l, r, i;
} query[LIM];

static inline bool compare(Query q1, Query q2) {
    return q1.l < q2.l || (q1.l == q1.l && q1.r < q2.r);
}

int N, K, M, i, arr[LIM];
int tree[LIM], ans[LIM];

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

static inline int prefix(int i) {
    int sum = 0;
    for (; i; i -= i & (-i))
        sum += tree[i];
    return sum;
}

static inline void set_value(int i, int val) {
    int curr = prefix(i) - prefix(i - 1);
    update(i, val - curr);
}

int main() {
    fin >> N >> K >> M;
    for (i = 1; i <= N; ++i)
        fin >> arr[i];

    for (i = 1; i <= M; ++i) {
        fin >> query[i].l >> query[i].r;
        query[i].i = i;
    }

    sort(query + 1, query + M + 1, compare);

    int l = 1, r = 0;
    for (i = 1; i <= M; ++i) {
        for (; l <= query[i].l; ++l)
            set_value(arr[l], 0);

        r = l;
        for (; r <= query[i].r; ++r)
            set_value(arr[r], arr[r]);

        ans[query[i].i] = prefix(K);
    }

    for (i = 1; i <= M; ++i)
        fout << ans[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}