#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 100002
#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second

int lst[NMAX];
int ARB[3*NMAX];
int A[NMAX];
int ans[NMAX];
vector< pair< pair<int, int>, int> > V;
int N, M, K;

void update(int nod, int st, int dr, int val, int poz)
{
	if (st == dr) ARB[nod] = val;
		else
		{
			int mid = (st + dr) / 2;

			if (poz <= mid) update(nod*2, st, mid, val, poz);
				else update(nod*2+1, mid+1, dr, val, poz);

			ARB[nod] = ARB[nod*2] + ARB[nod*2+1];
		}
}

int query(int nod, int st, int dr, int a, int b)
{
	if (a <= st && dr <= b) return ARB[nod];
		else 
		{
			int mid = (st + dr) / 2;
			int ans = 0;

			if (a <= mid) ans += query(nod*2, st, mid, a, b);
			if (b > mid) ans += query(nod*2+1, mid+1, dr, a, b);
			return ans;
		}
}

int main()
{
	freopen("distincte.in","r",stdin);
	freopen("distincte.out","w",stdout);

	int i, j, x, y, mx=0;

	scanf("%d %d %d", &N, &K, &M);

	for (i = 1; i <= N; i++)
		scanf("%d ", &A[i]);

	for (i = 1; i <= M; i++)
	{
		scanf("%d %d", &x, &y);
		V.pb( mp(mp(y, x), i) );
	}

	sort(V.begin(), V.end());

	for (i = 0; i < M; i++)
	{
		x = V[i].ff.ss; y = V[i].ff.ff;
	
		for (j = mx + 1; j <= y; j++)
			{
				if (lst[ A[j] ]) update(1, 1, N, 0, lst[ A[j] ]);
				lst[ A[j] ] = j;
				update(1, 1, N, A[j], j);
			}
		mx = y;
		ans[ V[i].ss ] = query(1, 1, N, x, y);
	}

	for (i = 1; i <= M; i++)
		printf("%d\n", ans[i]);
	return 0;
}