我没有处理分块操作，然而 $\verb!A!$ 了。（

//2022/1/27

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#include <cstring>//need "memset"

#include <algorithm>

#include <cmath>

#define int long long

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() cin.tie(0),cout.tie(0)

#define endl "\n"

#define Input_Int(n,a) for(register int i=1;i<=n;i++)scanf("%d",a+i);

#define Input_Long(n,a) for(register long long i=1;i<=n;i++)scanf("%lld",a+i);

#define mst(a,k) memset(a,k,sizeof(a))

namespace Newstd
{
	inline int read()
	{
		int x=0,k=1;
		char ch=getchar();
		while(ch<'0' || ch>'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=5e4+5;

struct Ask
{
	int l,r;

	int id;
};

Ask ask[ma];

int a[ma],bel[ma],cnt[ma],ans[ma];

int n,m,k;

int L,R,res;

namespace MO
{
	inline bool cmp(Ask x,Ask y)
	{
		if(bel[x.l]!=bel[y.l])
		{
			return bel[x.l]<bel[y.l];
		}

		return x.r<y.r;
	}

	inline void add(int p)
	{
		res=res+(2*cnt[a[p]]+1);

		cnt[a[p]]++;
	}

	inline void del(int p)
	{
		res=res-(2*cnt[a[p]]-1);

		cnt[a[p]]--;
	}
}

#undef int

int main(void)
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif

	#define int long long

	n=read(),m=read(),k=read();

	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
	}

	for(register int i=1;i<=m;i++)
	{
		ask[i].l=read(),ask[i].r=read();

		ask[i].id=i;
	}

	sort(ask+1,ask+m+1,MO::cmp);

	L=1,R=0,res=0;

	for(register int i=1;i<=m;i++)
	{
		while(L<ask[i].l)
		{
			MO::del(L++);
		}

		while(L>ask[i].l)
		{
			MO::add(--L);
		}

		while(R<ask[i].r)
		{
			MO::add(++R);
		}

		while(R>ask[i].r)
		{
			MO::del(R--);
		}

		ans[ask[i].id]=res;
	}

	for(register int i=1;i<=m;i++)
	{
		printf("%lld\n",ans[i]);
	}

	return 0;
}