大致思路就是在给定区间中用前面最近相同颜色的元素在区间内部的元素个数减去前面的前面在区间内部的元素个数即为答案，具体看代码。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;
int lst[MAXN],ss[MAXN],pre[MAXN];
struct node
{
	int tree[MAXN * 30],head[MAXN],ts,ls[MAXN * 30],rs[MAXN * 30];
	inline void update(int l,int r,int &q,int pre,int x)
	{
		q = ++ts;
		if (l == r)
		{
			tree[q] = tree[pre] + 1;
			return ;
		}
		int mid = (l + r) / 2;
		ls[q] = ls[pre],rs[q] = rs[pre];
		if (x <= mid) update(l,mid,ls[q],ls[pre],x);
		else update(mid + 1,r,rs[q],rs[pre],x);
		tree[q] = tree[ls[q]] + tree[rs[q]];
	}
	inline int query(int l,int r,int q,int pre,int x,int y)
	{
		if (x <= l && r <= y) return tree[q] - tree[pre];
		int mid = (l + r) / 2,sum = 0;
		if (x <= mid) sum = query(l,mid,ls[q],ls[pre],x,y);
		if (y > mid) sum += query(mid + 1,r,rs[q],rs[pre],x,y);
		return sum;
	}
}T,T2;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,Q,c,x,y;
	cin >> n >> c >> Q;
	for (int i = 1; i <= n; i++)
	{
		cin >> ss[i];
		pre[i] = lst[ss[i]];
		T.update(0,n,T.head[i],T.head[i - 1],lst[ss[i]]);
		lst[ss[i]] = i;
	}
	for (int i = 1; i <= n; i++) T2.update(0,n,T2.head[i],T2.head[i - 1],pre[pre[i]]);
	while (Q--)
	{
		cin >> x >> y;
		cout << T.query(0,n,T.head[y],T.head[x - 1],x,y) - T2.query(0,n,T2.head[y],T2.head[x - 1],x,y) << '\n';
	}
	return 0;
}