#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Interval {
    int x, y, ind;
};

class MyComp {
    public :
        bool operator () (const Interval &A, const Interval &B) {
            return A.y < B.y;
        }
};

Interval I [N];
int n, k, m;
int aib [N], last [N], a [N], ans [N];

inline int lsb (int x) {
    return x & (-x);
}

void update (int value, int i) {
    for (; i <= n; i = i + lsb (i))
        aib [i] += value;
}

int query (int i) {
    int s = 0;
    for (;i >= 1; i = i - lsb (i))
        s = s + aib [i];
    return s;
}

int main () {
    int i, j;

    freopen ("distincte.in", "r", stdin);
    freopen ("distincte.out", "w", stdout);

    scanf ("%d%d%d", &n, &k, &m);
    for (i = 1; i <= n; i ++)
        scanf ("%d", &a [i]);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &I [i].x, &I [i].y);
        I [i].ind = i;
    }
    sort (I + 1, I + 1 + m, MyComp ());
    j = 0;
    for (i = 1; i <= m; i ++) {
        while (j < I [i].y) {
            ++ j;
            if (last [a [j]] != 0)
                update (-a [j], last [a [j]]);
            update (a [j], j);
            last [a [j]] = j;
        }
        ans [I [i].ind] = query (I [i].y) - query (I [i].x - 1);
    }
    for (i = 1; i <= m; i ++)
        printf ("%d\n", ans [i]);
    return 0;
}