#include<fstream>
#include<algorithm>

#define NMAX 100005
#define MOD 666013

using namespace std;

ifstream f("distincte.in");
ofstream g("distincte.out");

struct Query {
	int ind , node1, node2 ;
}Q[NMAX];
int AIB[NMAX];
int N,M,v[NMAX],urm[NMAX],Sol[NMAX],K;

struct cmp {
	bool operator() (const Query &A , const Query &B ) const
	{
		if( A.node1 == B.node1 )
			return A.node2  > B.node2 ;
		return A.node1 > B.node1;
	
	}
};
inline int Lsb ( int x )
{
	return x&(-x);
}
inline int MODE( int value )
{
	if( value >= MOD )
		return value - MOD ;
	else
		if( value < 0 )
			value += MOD;
}
inline void Update ( int val , int node )
{
	for(;node <= N ; node +=  Lsb(node) )
	{
		AIB[node] += val ;
		MODE(AIB[node]);
	}
}
inline int QueryAib ( int node )
{
	int Answer = 0 ;
	for( ; node > 0 ; node -= Lsb(node) )
	{
		Answer += AIB[node];
		MODE(Answer);
	}
	return Answer;
}

int main ( void )
{
	int i , j ;
	f>>N>>K>>M;
	for( i = 1 ; i <= N ; ++i )
		f>>v[i];
	for( i = 1 ; i <= M ; ++i )
		f>>Q[i].node1>>Q[i].node2,Q[i].ind = i ;
	//sortez intervale pt a putea lucra mai usor
	//in AIB
	sort( Q + 1 ,Q + M + 1 , cmp() );
	for ( i = 1 , j = N ; i <= M ; ++i )
	{
		for( ; j >= Q[i].node1 ; --j )
		{
			Update(v[j],j);
			//scot urmatorul pt a pastra unicitiatea elementului pe interval
			if(urm[v[j]])
			Update(-v[j],urm[v[j]]);
			urm[v[j]] = j ;
		}
		Sol[Q[i].ind] = QueryAib(Q[i].node2);

	}
	for( i = 1 ; i <= M ; ++i )
		g<<Sol[i]<<"\n";
	f.close();
	g.close();
	return 0;
}