关于long long

#include <bits/stdc++.h>
using namespace std;
int n,m,k,ans;
int B;
int a[50005];
int c[50005];
int l = 1,r = 0;
struct node
{
	int l,r,id,ans;
	bool operator<(const node &a)const
	{
		if((l+B-1)/B != (a.l+B-1)/B)
		{
			return (l+B-1)/B < (a.l+B-1)/B;
		}
		return r < a.r;
	}
};
node qr[50005];
void adr()
{
	r++;
	c[a[r]]++;
	ans += 2*c[a[r]]-1;
	return;
}
void adl()
{
	l--;
	c[a[l]]++;
	ans += 2*c[a[l]]-1;
	return;
}
void der()
{
	c[a[r]]--;
	ans -= 2*c[a[r]]+1;
	r--;
	return;
}
void del()
{
	c[a[l]]--;
	ans -= 2*c[a[l]]+1;
	l++;
	return;
}
bool cmp(node x,node y)
{
	return x.id < y.id;
}
int main()
{
	cin >> n >> m >> k;
	B = sqrt(n);
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	for(int i = 1;i <= m;i++)
	{
		cin >> qr[i].l >> qr[i].r;
		qr[i].id = i;
	}
	sort(qr+1,qr+m+1);
	for(int i = 1;i <= m;i++)
	{
		while(r < qr[i].r)
		{
			adr();
		}
		while(r > qr[i].r)
		{
			der();
		}
		while(l > qr[i].l)
		{
			adl();
		}
		while(l < qr[i].l)
		{
			del();
		}
		qr[i].ans = ans;
	}
	sort(qr+1,qr+m+1,cmp);
	for(int i = 1;i <= m;i++)
	{
		cout << qr[i].ans << "\n";
	}
	return 0;
}