#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, q, k, l, r, num, a[N], b[N], cnt[N], ans[N];
struct node
{
	int l, r, id;
}s[N];
bool cmp(node x, node y)
{
	if(b[x.l] != b[y.l])
		return x.l < y.l;
	if(b[x.l] & 1)
		return x.r < y.r;
	else
		return x.r > y.r;
}
void add(int k)
{
	num += 2 * cnt[a[k]] + 1;
    ++cnt[a[k]];
}
void del(int k)
{
	num -= 2 * cnt[a[k]] - 1;
    --cnt[a[k]];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> q >> k;
	int len = sqrt(n);
	for(int i = 1;i <= n;i++)
		cin >> a[i], b[i] = (i - 1) / len + 1;
	for(int i = 1;i <= q;i++)
		cin >> s[i].l >> s[i].r, s[i].id = i;
	sort(s + 1, s + q + 1, cmp);
	for(int i = 1;i <= q;i++)
	{
		while(s[i].l < l) add(--l);
        while(s[i].r > r) add(++r);
		while(s[i].l > l) del(l++);
		while(s[i].r < r) del(r--);
		ans[s[i].id] = num;
	}
	for(int i = 1;i <= q;i++)
		cout << ans[i] - 1 << "\n";
	return 0;
}

为什么要减一才能过