#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define lc(x) t[x].l

#define rc(x) t[x].r

const int N=1e6+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n, k, Q, a[N], last[N], pos[N], l, r;

struct ChairTree{

    struct meow{int l, r, sum;} t[N*];

    int sz, root[N];

    void ins(int &x, int l, int r, int p) {

        t[++sz] = t[x]; x=sz;

        t[x].sum++;

        if(l==r) return;

        int mid = (l+r)>>;

        if(p<=mid) ins(t[x].l, l, mid, p);

        else ins(t[x].r, mid+, r, p);

    }

    int que(int x, int y, int l, int r, int ql, int qr) {

        if(ql<=l && r<=qr) return t[y].sum - t[x].sum;

        else {

            int mid=(l+r)>>, ans=;

            if(ql<=mid) ans += que(lc(x), lc(y), l, mid, ql, qr);

            if(mid<qr)  ans += que(rc(x), rc(y), mid+, r, ql, qr);

            return ans;

        }

    }

}C1, C2;

int main() {

    freopen("in","r",stdin);

    n=read(); k=read(); Q=read();

    for(int i=; i<=n; i++) a[i]=read(), last[i] = pos[a[i]], pos[a[i]] = i;

    for(int i=; i<=n; i++) {

        C1.root[i] = C1.root[i-], C1.ins(C1.root[i], , n, last[i]);

        C2.root[i] = C2.root[i-], C2.ins(C2.root[i], , n, last[last[i]]);

    }

    for(int i=; i<=Q; i++)

        l=read(), r=read(),

        printf("%d\n", C1.que(C1.root[l-], C1.root[r], , n, l, r) - C2.que(C2.root[l-], C2.root[r], , n, l, r) );

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define lc(x) t[x].l

#define rc(x) t[x].r

const int N=1e6+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n, k, Q, a[N], last[N], pos[N], l, r;

int c[N];

inline void add(int p, int v) {if(p!=) for(;p<=n;p+=(p&-p)) c[p]+=v;}

inline int sum(int p) {int ans=; for(;p;p-=(p&-p)) ans+=c[p]; return ans;}

struct meow{

    int l, r, qid;

    bool operator <(const meow &a) const {return r<a.r;}

}q[N];

int ans[N], now;

int main() {

    freopen("in","r",stdin);

    n=read(); k=read(); Q=read();

    for(int i=; i<=n; i++) a[i]=read();

    for(int i=; i<=Q; i++) l=read(), r=read(), q[i]=(meow){l, r, i};

    sort(q+, q++Q);

    now = ;

    for(int i=; i<=n; i++) {

        last[i] = pos[a[i]]; pos[a[i]] = i;

        add(last[i], ); add(last[last[i]], -);

        while(q[now].r == i) ans[q[now].qid] = sum(i) - sum(q[now].l-), now++;

    }

    for(int i=; i<=Q; i++) printf("%d\n", ans[i]);

}