#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 , MODR = 666013;
int pv[MAXN + 1] , nv[MAXN + 1] , v[MAXN + 1] , ans[MAXN + 1] , n , aib[MAXN + 1];
map < int , int > uv;
struct query {
    int i , l , r;
} q[MAXN + 1];
bool cmp ( query a , query b ) {
    return a.l < b.l; // restul nu conteaza
}
int lsb ( int x ) {
    return x & -x;
}
void update ( int poz , int val ) {
    while ( poz <= n ) {
        aib[poz] += val;
        poz += lsb ( poz );
    }
}
long long query ( int poz ) {
    long long ansq;

    ansq = 0;
    while ( poz > 0 ) {
        ansq += aib[poz];
        poz -= lsb ( poz );
    }

    return ansq;
}
int main () {
    ifstream cin ( "distincte.in" );
    ofstream cout ( "distincte.out" );
    int k , m , i , j;

    cin >> n >> k >> m;
    for ( i = 1 ; i <= n ; i++ ) {
        cin >> v[i];
        if ( uv.find ( v[i] ) != uv.end () )
            nv[uv[v[i]]] = i;
        else
            update ( i , 1 );
        uv[v[i]] = i;
        nv[i] = -1;
    }
    for ( i = 0 ; i < m ; i++ ) {
        cin >> q[i].l >> q[i].r;
        q[i].i = i;
    }
    sort ( q , q + m , cmp );
    j = 1;
    for ( i = 0 ; i < m ; i++ ) {
        while ( j < q[i].l ) {
            update ( j , -1 );
            if ( nv[j] != -1 )
                update ( nv[j] , 1 );
            j++;
        }
        ans[q[i].i] = query ( q[i].r ) % MODR;
    }
    for ( i = 0 ; i < m ; i++ )
        cout << ans[i] << '\n';
    return 0;
}