#include<bits/stdc++.h>
using namespace std;
long long n,a[1000006],m,k,as[1000006],pl,pr,ps,t[1000006];
struct nm{
    long long l,r,p;
}b[1000006];
bool c(nm x,nm y){
    if(x.l/1000==y.l/1000) return x.r<y.r;
    return x.l<y.l;
}
int main(){
    freopen("1flower.in","r",stdin);
    freopen("1flower.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) 
        cin>>b[i].l>>b[i].r,b[i].p=i;
    sort(b+1,b+m+1,c),t[0]=1e9;
    for(int i=1;i<=m;i++){
        if(b[i-1].r<b[i].r){
            for(int j=b[i-1].r+1;j<=b[i].r;j++)
                if(t[a[j]]++==1) ps++;
        }else{
            for(int j=b[i].r+1;j<=b[i-1].r;j++)
                if(--t[a[j]]==1) ps--;
        }
        if(b[i-1].l<b[i].l){
            for(int j=b[i-1].l;j<b[i].l;j++)
                if(--t[a[j]]==1) ps--;
        }else{
            for(int j=b[i].l;j<b[i-1].l;j++)
                if(t[a[j]]++==1) ps++;
        }
        as[b[i].p]=ps;
    }
    for(int i=1;i<=m;i++) cout<<as[i]<<"\n";
    return 0;
}