#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
inline void read(int &x)
{
    int sum=0;
    char c=getchar();
    while (c<'0'||c>'9')
    {
        c=getchar();
    }
    while ('0'<=c&&c<='9')
    {
        sum=sum*10+(c-'0');
        c=getchar();
    }
    x=sum;
}
int n,t,q,len,cnt[N],a[N],v[N],id[N],l=1,r=0,ret=0;
struct node {
    int l,r,id;
} c[N];
inline int cmd(node x,node y)
{
    if (id[x.l]==id[x.r])
    {
        if (id[x.l]%2==1)
        {
            return x.r<y.r;
        }
        else
        {
            return x.r>y.r;
        }
    }
    return id[x.l]<id[y.l];
}
inline void change(int x,int c)
{
    cnt[a[x]]+=c;
    if(c>0)
    {
        ret+=(cnt[a[x]]==2);
    }
    else
    {
        ret-=(cnt[a[x]]==1);
    }
}
int main() {
    freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    read(n),read(t),read(q);
    len=sqrt(n);
    for (register int i=1;i<=n;i++)
    {
        read(a[i]);
        id[i]=i/len+1;
    }
    for (register int i=1;i<=q;i++)
    {
        read(c[i].l),read(c[i].r);
        c[i].id=i;
    }
    sort(c+1,c+q+1,cmd);
    for (register int i=1;i<=q;i++)
    {
        while (l<c[i].l) change(l,-1),l++;
        while (l>c[i].l) change(l-1,1),l--;
        while (r<c[i].r) change(r+1,1),r++;
        while (r>c[i].r) change(r,-1),r--;
        v[c[i].id]=ret;
    }
    for (register int i=1;i<=q;i++)
    {
        printf("%d\n",v[i]);
    }
}