#include<bits/stdc++.h>
using namespace std;
auto IN = freopen("1flower.in", "r", stdin);
auto OUT = freopen("1flower.out", "w", stdout);
auto IOS = ios::sync_with_stdio(false);
auto CIN = cin.tie(nullptr);
int mread(){
    int x = 0, f = 1;
    char c = cin.get();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = cin.get();
    }
    while(c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = cin.get();
    }
    return x * f;
}
const int N = 1e6 + 5;
int n = mread(), c = mread(), m = mread();
struct node{
    int l, r, id;
}s[N];
int a[N], la[N], ans[N], s2[N];
void add(int x, int k){
    while(x <= n){
        s2[x] += k;
        x += x & -x;
    }
    return;
}
int query(int x){
    int ans = 0;
    while(x){
        ans += s2[x];
        x -= x & -x;
    }
    return ans;
}
int t[N];
signed main(){
    for(int i = 1; i <= n; i ++){
        a[i] = mread();
    }
    for(int i = 1; i <= m; i ++){
        s[i].l = mread(), s[i].r = mread(), s[i].id = i;
    }
    sort(s + 1, s + 1 + m, [](node a, node b){
        return a.r < b.r;
    });
    for(int i = 1, j = 1; i <= n; i ++){
        if(la[a[i]] == 0){
            la[a[i]] = i;
        }
        else{
            if(t[a[i]]){
                add(t[a[i]], -1);
            }
            t[a[i]] = la[a[i]];
            la[a[i]] = i;
            add(t[a[i]], 1);
        }
        while(j <= m && s[j].r == i){
            ans[s[j].id] = query(n) - query(s[j].l - 1);
            j ++;
        }
    }
    for(int i = 1; i <= m; i ++){
        cout << ans[i] << "\n";
    }
    return 0;
}