#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + ;

struct Que

{

        int l , r , id;

} q[MAXN];

int n , c , m;

int a[MAXN] , ans[MAXN] , pre[MAXN] , nxt[MAXN];

bool visited[MAXN]; 

struct Binary_Indexed_Tree

{

        int c[MAXN];

        inline int lowbit(int x)

        {

                return x & (-x);

        }

        inline void add(int pos,int value)

        {

                if (!pos) return;

                for (int i = pos; i <= n; i += lowbit(i))

                        c[i] += value;

        }

        inline int query(int pos)

        {

                int ret = ;

                if (!pos) return ;

                for (int i = pos; i; i -= lowbit(i))

                        ret += c[i];

                return ret;

        }

        inline int query(int l,int r)

        {

                return query(r) - query(l - );

        }

} bit;

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline bool cmp(Que a,Que b)

{

        return a.l < b.l;

}

int main()

{

        read(n); read(c); read(m);

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

        for (int i = n; i >= ; i--)

        {

                if (!visited[a[i]])

                {

                        visited[a[i]] = true;

                        pre[a[i]] = i;

                        continue;

                }    else

                {

                        nxt[i] = pre[a[i]];

                        pre[a[i]] = i;

                }

        }

        memset(visited,false,sizeof(visited));

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

        {

                if (!visited[a[i]])

                {

                        bit.add(nxt[i],);

                        visited[a[i]] = true;

                }

        }

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

        {

                read(q[i].l); read(q[i].r);

                q[i].id = i;

        }

        sort(q + ,q + m + ,cmp);

        int cur = ;

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

        {

                while (cur < q[i].l)

                {

                        bit.add(nxt[cur],-);

                        bit.add(nxt[nxt[cur]],);

                        ++cur;

                }

                ans[q[i].id] = bit.query(q[i].r) - bit.query(q[i].l - );

        }

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

        return ;

}