这个题我写的树状数组，快读快写都用上了，166分最后一个点死活过不去555555555555555555555

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
#define IL inline
#define ri register int

const int N = 2e6 + 10;

int n,c,m;
struct ask {
	int l,r,id;
	bool operator < (const ask& rhs) const {
		return r < rhs.r;
	}
}q[N];

int a[N],C[N],ans[N],pre[2][N];

template <typename T>
IL T read(T& x) {
	x=0;int f=1; char ch = getchar();
	while(!isdigit(ch)){if(ch == '-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int buf[22];
template <typename T>
IL void write(T i){
	int p = 0;
	if(i<0){putchar('-'); i=-i;}
	if(i==0){p++;buf[0]=0;}
	else while(i) {
		buf[p++] = i % 10;
		i /= 10;
	}
	for(int j=p-1;j>=0;j--) putchar('0'+buf[j]);
}

IL int lb(int x) {return x&(-x);}
IL void add(int x,int v) { for(int i=x;i<=n;i+=lb(i)) C[i] += v;}
IL int sum(int x) {
	int ret = 0;
	for(int i=x;i;i-=lb(i)) ret += C[i];
	return ret;
}
IL int query(int l,int r) { return sum(r) - sum(l-1);}
int main() {
	read(n); read(c); read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=m;i++) {
		read(q[i].l); read(q[i].r);
		q[i].id = i;
	}
	sort(q+1,q+1+m);
	for(int i=1,j=1;i<=m;i++) {
		int l = q[i].l, r = q[i].r, id = q[i].id;
		for(;j<=r;j++) {
			if(!pre[0][a[j]]) {
				pre[0][a[j]] = j;
			}
			else if(!pre[1][a[j]]) {
				pre[1][a[j]] = j; add(pre[0][a[j]],1);
			}
			else {
				add(pre[0][a[j]],-1);
				add(pre[1][a[j]],1);
				pre[0][a[j]] = pre[1][a[j]];
				pre[1][a[j]] = j;
			}
		}
		ans[id] = query(l,r);
	}
	for(int i=1;i<=m;i++) {write(ans[i]); putchar('\n');}
	return 0;
}