#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 2000010

int n,m,c,a[N],nxt[N],p[N],tree[N],ans[N],flag[N];

struct data

{

    int l,r,i;

    bool operator <(const data&a) const

    {

        return l<a.l;

    }

}q[N];

void add(int k,int x){while (k<=n) tree[k]+=x,k+=k&-k;}

int sum(int k){int s=;while (k) s+=tree[k],k-=k&-k;return s;}

int main()

{

#ifndef ONLINE_JUDGE

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

    freopen("bzoj2743.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),c=read(),m=read();

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

    {

        a[i]=read(),nxt[p[a[i]]]=i,p[a[i]]=i;

        if (flag[a[i]]==) add(i,),flag[a[i]]=;

        else if (!flag[a[i]]) flag[a[i]]=;

    }

    for (int i=;i<=n+;i++) if (!nxt[i]) nxt[i]=n+;

    for (int i=;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].i=i;

    sort(q+,q+m+);

    q[].l=;

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

    {

        while (q[i].l>q[i-].l)

        add(nxt[q[i-].l],-),add(nxt[nxt[q[i-].l]],),q[i-].l++;

        ans[q[i].i]=sum(q[i].r)-sum(q[i].l-);

    }

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

    return ;

}