#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Occ {
    ll x;
    int pos;
};

struct Query {
    int l, r, id;
};

struct Fenwick {
    int n;
    vector<ll> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void dodaj(int i, ll v) {
        for (; i <= n; i += i & -i)
            bit[i] += v;
    }

    void dodaj_przedzial(int l, int r, ll v) {
        if (l > r) return;

        dodaj(l, v);
        dodaj(r + 1, -v);
    }

    ll odczytaj(int i) {
        ll wynik = 0;

        for (; i > 0; i -= i & -i)
            wynik += bit[i];

        return wynik;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k, q;
    cin >> n >> k >> q;

    vector<ll> a(n + 1);
    vector<Occ> wyst(n);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        wyst[i - 1] = {a[i], i};
    }

    // Sortujemy wystąpienia według wartości, a następnie pozycji.
    sort(wyst.begin(), wyst.end(), [](Occ x, Occ y) {
        if (x.x != y.x) return x.x < y.x;
        return x.pos < y.pos;
    });

    vector<int> poprzednie(n + 1, 0);
    vector<int> pk(n + 1, 0);
    vector<int> pk1(n + 1, 0);

    // Wyznaczamy potrzebne wcześniejsze wystąpienia.
    int start = 0;

    while (start < n) {
        int koniec = start + 1;

        while (koniec < n &&
               wyst[koniec].x == wyst[start].x) {
            koniec++;
        }

        for (int j = start; j < koniec; j++) {
            int i = wyst[j].pos;
            int t = j - start + 1;

            // Poprzednie wystąpienie p_(t-1).
            if (t >= 2)
                poprzednie[i] = wyst[j - 1].pos;

            // p_(t-k).
            if (t > k)
                pk[i] = wyst[j - k].pos;

            // p_(t-k-1).
            if (t > k + 1)
                pk1[i] = wyst[j - k - 1].pos;
        }

        start = koniec;
    }

    vector<Query> zap(q);

    for (int i = 0; i < q; i++) {
        cin >> zap[i].l >> zap[i].r;
        zap[i].id = i;
    }

    sort(zap.begin(), zap.end(), [](Query x, Query y) {
        return x.r < y.r;
    });

    Fenwick fenwick(n);
    vector<ll> wynik(q);

    int j = 0;

    for (int i = 1; i <= n; i++) {
        // Usuwamy wkład z lewych końców, które
        // przestały spełniać warunek.
        fenwick.dodaj_przedzial(
            pk1[i] + 1, pk[i], -a[i]
        );

        // Dodajemy wkład na nowych lewych końcach.
        fenwick.dodaj_przedzial(
            poprzednie[i] + 1, i, a[i]
        );

        // Odpowiadamy na zapytania z prawym końcem i.
        while (j < q && zap[j].r == i) {
            wynik[zap[j].id] =
                fenwick.odczytaj(zap[j].l);
            j++;
        }
    }

    for (int i = 0; i < q; i++)
        cout << wynik[i] << '\n';

    return 0;
}