如题。

import math

n, m, k = map(int, input().split())
ar = list(map(int, input().split()))
ar.insert(0, 0)
class que:
    def __init__(self, la, r, id, d):
        self.la = la
        self.r = r
        self.id = id
        self.d = d

q = []
blocksize = int(math.sqrt(n))
for df in range(1, 1+m):
    a, b = map(int, input().split())
    q.append(que(a, b, df//blocksize, df))
q = sorted(q, key = lambda x:(x.id, x.r))
si = int(5e4+56)
cnt, ans = [0] * si, [0] * si
la, r = q[0].la, q[0].la - 1
global temp
temp = 0

def delete(x):
    global temp
    cnt[ar[x]] -= 1
    temp -= 2 * cnt[ar[x]] + 1

def add(x):
    global temp
    cnt[ar[x]] += 1
    temp += 2 * cnt[ar[x]] - 1

for i in range(len(q)):
    while la < q[i].la:
        delete(la)
        la += 1
    while la > q[i].la:
        la -= 1
        add(la)
    while r > q[i].r:
        delete(r)
        r -= 1
    while r < q[i].r:
        r += 1
        add(r)
    ans[q[i].d] = temp

for i in range(1, m+1):
    print(ans[i])