//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=200005;

/*struct segTreeNode
{
	int lazy, max, left, right, len;
	friend segTreeNode operator+(segTreeNode a, segTreeNode b)
	{
		segTreeNode x;
		x.lazy=-1;
		x.max=std::max(std::max(a.max, b.max), a.right+b.left);
		if(a.len==a.left && a.left+b.left>x.max)
			x.max=a.left+b.left;
		if(b.len==b.right && a.right+b.right>x.max)
			x.max=a.right+b.right;
		x.left=a.left+b.left*(a.left==a.len);
		x.right=b.right+a.right*(b.right==b.len);
		x.len=a.len+b.len;
		return x;
	}
};*/
typedef long long int segTreeNode;
struct segTree
{
	int N;
	segTreeNode v[NMAX<<2];

	void init(int _N, segTreeNode* _v)
	{
		N=_N;
		build(0, 0, N-1, _v);
	}

	void initDefault(int _N, segTreeNode& defaultVal)
	{
		N=_N;
		buildDefault(0, 0, N-1, defaultVal);
	}

	void build(int node, int l, int r, segTreeNode* _v)
	{
		if(l==r)
		{
			v[node]=_v[l];
		}
		else
		{
			const int mid=l+((r-l)>>1);
			build((node<<1)|1, l, mid, _v);
			build((node<<1)+2, mid+1, r, _v);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}

	void buildDefault(int node, int l, int r, segTreeNode& defVal)
	{
		if(l==r)
		{
			v[node]=defVal;
		}
		else
		{
			const int mid=l+((r-l)>>1);
			buildDefault((node<<1)|1, l, mid, defVal);
			buildDefault((node<<1)+2, mid+1, r, defVal);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}

	/*void propag(int node, int l, int r)
	{
		if(v[node].lazy!=-1)
		{
			if(l!=r)
			{
				v[(node<<1)|1].lazy=v[node].lazy;
				v[(node<<1)+2].lazy=v[node].lazy;
			}
			if(v[node].lazy)
				v[node].max=v[node].left=v[node].right=0;
			else
				v[node].max=v[node].left=v[node].right=v[node].len;
			v[node].lazy=-1;
		}
	}*/

	segTreeNode query(int l, int r) {return query(0, 0, N-1, l, r);}
	segTreeNode query(int node, int l, int r, int st, int dr)
	{
		//propag(node, l, r);
		if(st<=l && r<=dr)
			return v[node];
		const int mid=l+((r-l)>>1);
		if(dr<=mid)
			return query((node<<1)|1, l, mid, st, dr);
		if(mid<st)
			return query((node<<1)+2, mid+1, r, st, dr);
		return query((node<<1)|1, l, mid, st, dr)+query((node<<1)+2, mid+1, r, st, dr);
	}

	/*int findKth0(int K) {return findKth0(0, 0, N-1, K);}
	int findKth0(int node, int l, int r, int K)
	{
		if(l==r)
			return l;
		int mid=l+((r-l)>>1);
		if(mid-l+1-v[(node<<1)|1].x>K)
			return findKth0((node<<1)|1, l, mid, K);
		return findKth0((node<<1)+2, mid+1, r, K-(mid-l+1-v[(node<<1)|1].x));
	}*/

	/*void update(int l, int r, segTreeNode& x) {update(0, 0, N-1, l, r, x);}
	void update(int node, int l, int r, int st, int dr, segTreeNode& x)
	{
		//propag(node, l, r);
		if(st<=l && r<=dr)
		{
			v[node].lazy=x.lazy;
		}
		else
		{
			const int mid=l+((r-l)>>1);
			if(st<=mid)
				update((node<<1)|1, l, mid, st, dr, x);
			if(mid<dr)
				update((node<<1)+2, mid+1, r, st, dr, x);
			//propag((node<<1)|1, l, mid);
			//propag((node<<1)+2, mid+1, r);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}*/

	void update(int pos, segTreeNode& x) {update(0, 0, N-1, pos, x);}
	void update(int node, int l, int r, int pos, segTreeNode& x)
	{
		if(l==r)
		{
			v[node]=x;
		}
		else
		{
			const int mid=l+((r-l)>>1);
			if(pos<=mid)
				update((node<<1)|1, l, mid, pos, x);
			else
				update((node<<1)+2, mid+1, r, pos, x);
			v[node]=v[(node<<1)|1]+v[(node<<1)+2];
		}
	}
};
segTree S;
int v[NMAX], prev[NMAX];
struct query
{
	int l, r, i;
	friend bool operator<(query a, query b)
	{
		return a.r<b.r;
	}
};
query q[NMAX];
long long int ans[NMAX];

int main()
{
	FILE *f=fopen("distincte.in", "r");
	FILE *g=fopen("distincte.out", "w");
	int N, _, i, j;
	long long int x;
	fscanf(f, "%d%*d%d", &N, &_);
	for(i=0;i<N;++i)
		fscanf(f, "%d", v+i), prev[v[i]]=-1;
	for(i=0;i<_;++i)
		fscanf(f, "%d%d", &q[i].l, &q[i].r), --q[i].l, --q[i].r, q[i].i=i;
	std::sort(q, q+_);
	x=0;
	S.initDefault(N, x);
	for(i=j=0;j<_;++j)
	{
		while(i<=q[j].r)
		{
			x=prev[v[i]];
			if(x!=-1)
			{
				x=0;
				S.update(prev[v[i]], x);
			}
			x=v[i];
			S.update(i, x);
			prev[v[i]]=i;
			++i;
		}
		ans[q[j].i]=S.query(q[j].l, q[j].r);
	}
	for(i=0;i<_;++i)
		fprintf(g, "%lld\n", ans[i]);
	fclose(f);
	fclose(g);
	return 0;
}