#include <bits/stdc++.h>
#define fr first
#define sc second
#define ebk emplace_back
 
using namespace std;

const int N = 5e4 + 12;
typedef pair<int, int> pii;

int n, m, k;
int arr[N];
long long ans[N], cnt[N], block=1, res = 0;
long long L = 1, R; // 不是很懂 为什么 L 要从 1 开始 

/*
	ans[] 对于每一个区间的答案
	cnt[] 当前区间里 数字 i 出现的次数
	block 分块长度
	res 当前答案
	移动 L R 维护依次上升的区间
*/

struct node
{
	int l;
	int r;
	int id;
	
}qir[N];

bool cmp(const node &a, const node &b)
{
	if (a.l/block == b.l/block) return a.r < b.r;
	return a.l/block < b.l/block;
}

inline void add(int idx) // res 添加一个 idx 
{
	int x = arr[idx];
	cnt[x] ++;
	res += cnt[x]*2 - 1;
}

inline void del(int idx) 	// res 删除一个 idx 
{
	int x = arr[idx];
	cnt[x] --;	
	res -= cnt[x]*2 + 1;
}


int main ()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int a, b;
	cin >> n >> m >> k;
	
	for (int i=1;i <= n;i ++) cin >> arr[i];
	
	for (int i=0;i < m;i ++)
	{
		cin >> qir[i].l >> qir[i].r;
		qir[i].id = i;
	}
	
	block = sqrt(n); 
	
	sort(qir, qir + m, cmp); // 排序区间集 
	
	for (int i=0;i < m;i ++) // 区间集 从 [0, m) 
	{
		while (L > qir[i].l) add( -- L );
		
		while (R < qir[i].r) add( ++ R );
		
		while (L < qir[i].l) del( L ++ );

		while (R > qir[i].r) del( R -- );
		
		ans[qir[i].id] = res;
 	}
	
	for (int i=0;i < m;i ++)
		cout << ans[i] << endl;
		
	return 0;
}

如果 L 从 0 开始 也就多执行一次while，而且arr[0] 没有值 为什么会wa