#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cmath>

using namespace std;

#define N 1000005

int n,m,a[N],vis[N],nxt[N],sum[N];

int find(int x)

{

    int ret=0;

    for(int i=x;i;i-=i&-i)ret+=sum[i];

    return ret;

}

void fix(int x,int c)

{

    for(int i=x;i<N;i+=i&-i)sum[i]+=c;

}

struct node

{

    int idx,l,r,ans;

}q[N];

bool cmp(const node &a,const node &b){return a.l<b.l;}

bool cmp1(const node &a,const node &b){return a.idx<b.idx;}

int main()

{

    scanf("%d%*d%d",&n,&m);

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

    {

        scanf("%d",&a[i]);

        if(vis[a[i]])nxt[vis[a[i]]]=i;

        vis[a[i]]=i;

    }

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

    {

        scanf("%d%d",&q[i].l,&q[i].r);q[i].idx=i;

    }

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

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

    {

        if(nxt[i])fix(nxt[i],1);

        if(nxt[nxt[i]]) fix(nxt[nxt[i]],-1);

    }

    int h=1;

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

    {

        while(q[h].l==i)q[h].ans=find(q[h].r)-find(i-1),h++;

        if(nxt[i])fix(nxt[i],-1);

        if(nxt[nxt[i]])fix(nxt[nxt[i]],1);

    }

    sort(q+1,q+m+1,cmp1);

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

    {

        printf("%d\n",q[i].ans);

    }

    return 0;

}