Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            elif a[c[1]][0] > c[2]:
                a[c[1]].appendleft(c[2])
            else:
                left = 0
                right = len(a[c[1]])
                while right - left > 1:
                    mid = (right - left)//2
                    if a[c[1]][mid] < c[2]:
                        left = mid
                    else:
                        right = mid
                a[c[1]].insert(right, c[2])
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()




### FIXED CODE ###

import heapq

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        heapq.heappush(a[c[1]],-c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(-a[c[1]][0])
    else:
        if a[c[1]]:
            heapq.heappop(a[c[1]])
### BUGGY CODE ###

from collections import deque
n = int(input())
P = list(map(int, input().split()))
MAP = [['#']*n for _ in range(n)]
INF = 10**18
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def bfs(init_v):
    next_v = deque([init_v])
    dist = [[INF]*n for _ in range(n)]
    i, j = init_v
    dist[i][j] = 0
    MAP[i][j] = '.'
    mincost = INF
    while next_v:
        i, j = next_v.popleft()
        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                if dist[i][j] < mincost:
                    mincost = dist[i][j]
                continue
            cost = 0 if MAP[x][y] == '.'else 1
            if dist[x][y] <= dist[i][j]+cost:
                continue
            dist[x][y] = dist[i][j]+cost
            next_v.append((x, y))
    return dist, mincost


def to_idx(p):
    i, j = divmod(p-1, n)
    return i, j


ans = 0
for p in P:
    dist, mincost = bfs(to_idx(p))
    ans += mincost
print(ans)


### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

# AC by Pypy not Python
# Pythonで通すためには,  npで配列毎まるっと処理する必要あり

N, W = map(int, input().split())

dp = [0] * (W+1) # DP枠_重さ’0’～'W'まで準備

for i in range(N):
    w, v = map(int, input().split()) # 商品, 各々重さと価値
    tmp = dp[:] # ひとつ前の商品までのDP枠を参照用にコピー
    for j in range(1, W+1): # 各商品のDP枠への落とし込み
        if j  >= w and tmp[j] < tmp[j-w] + v: # 商品の重さよりDP枠の重さが重い場合で...
            dp[j] = tmp[j-w] + v # この商品を加え, 合計価値が up する場合は replace
        else: # 商品の重さよりDP枠の重さが軽い場合と, ↑で価値が up しない場合は...
            dp[j] = tmp[j] # ↑ 参照データをそのままコピー
    
print(dp[-1])


### FIXED CODE ###

N, W = map(int, input().split())

w, v = [0] * N, [0] * N

for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
		else:
		    dp[i + 1][j] = dp[i][j] 

print(dp[N][W])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import Counter

n = int(input())
a = list(map(int, input().split()))

dic = Counter(a)

ans = 0

memo = {}

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        for i in range(1, int(ai**0.5)+1):
            if ai % i == 0:
                d = i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break
                if i != ai // i:
                    d = ai // i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)
    

            




### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print(sum(memo))
### BUGGY CODE ###

from functools import lru_cache as cache
from bisect import bisect

n = int(input())
a_list = sorted(map(int, input().split()))
b_list = sorted(map(int, input().split()))
c_list = sorted(map(int, input().split()))

b_c_table = [n - bisect(c_list, b) for b in b_list]

@cache(maxsize=None)
def sum_(*list_):
    return sum(list(list_))

ans = 0
for a in a_list:
    i = bisect(b_list, a)
    ans += sum_(*b_c_table[i:n])
print(ans)

### FIXED CODE ###

from bisect import bisect
from itertools import accumulate

n = int(input())
a_list = sorted(map(int, input().split()))
b_list = sorted(map(int, input().split()))
c_list = sorted(map(int, input().split()))

b_c_table_ = list(accumulate(reversed(tuple(n - bisect(c_list, b) for b in b_list))))
b_c_table_.reverse()
b_c_table_ += [0]

print(sum(b_c_table_[bisect(b_list, a)] for a in a_list))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input().strip()+'#' for i in range(h)]+['#'*(w+2)]
dp = [[[0]*2 for i in range(w+2)] for i in range(h+2)]
cnt = 0
ans = 0

def dfsw(x,y,cnt):
  if l[x][y+1] == '.':
    cnt += 1
    dp[x][y][0] = dfsw(x,y+1,cnt)
    return dp[x][y][0]
  else:
    dp[x][y][0] = cnt
    return dp[x][y][0]

def dfsh(x,y,cnt):
  if l[x+1][y] == '.':
    cnt += 1
    dp[x][y][1] = dfsh(x+1,y,cnt)
    return dp[x][y][1]
  else:
    dp[x][y][1] = cnt
    return dp[x][y][1]

for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.' and dp[i][j][0] == 0:
      dfsw(i,j,1)
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.' and dp[i][j][1] == 0:
      dfsh(i,j,1)
    
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans, sum(dp[i][j]) - 1)
print(ans)

### FIXED CODE ###

import numpy as np
h,w = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
#print(ar)
l = np.zeros((h,w),dtype=int)
r = np.zeros((h,w),dtype=int)
u = np.zeros((h,w),dtype=int)
d = np.zeros((h,w),dtype=int)

for i in range(h):
  u[i] = (u[i-1]+1)*ar[i]
  #print(u)
  d[-i-1] = (d[-i]+1)*ar[-i-1]
  #print(d)
  
for j in range(w):
  l[:,j] = (l[:,j-1]+1)*ar[:,j]
  #print(l)
  r[:,-j-1] = (r[:,-j]+1)*ar[:,-j-1]
  #print(r)
print(np.max(u+d+l+r)-3)
### BUGGY CODE ###

K = int(input())
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
g = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            g += gcd(i,j,k)
print(g)


### FIXED CODE ###

K = int(input())
import math
g = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            if i == j and j == k:
                g += math.gcd(math.gcd(i,j),k)
            elif i == j and j != k:
                g += math.gcd(math.gcd(i,j),k) * 3
            elif i != j and j == k:
                g += math.gcd(math.gcd(i,j),k) * 3
            else:
                g += math.gcd(math.gcd(i,j),k) * 6


print(g)
### BUGGY CODE ###

def solve():
    N = int(input())
    A = input().split()
    b = []
    for i,a in enumerate(A):
        if i%2 == 0:
            b.append(a)
        else:
            b.insert(0, a)

    if N % 2 == 1:
        b.reverse()
    print(' '.join(b))
    
solve()

### FIXED CODE ###

def solve():
    N = int(input())
    A = map(int, input().split())
    b = []
    left = []
    right = []
    for i,a in enumerate(A):
        if i%2 == 0:
            right.append(a)
        else:
            left.append(a)
            # b.insert(0, a)

    if N % 2 == 1:
        right.reverse()
        b = right+left
    else:
        left.reverse()
        b = left + right
    print(' '.join(map(str, b)))
    
solve()
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))

    for _ in range(M):
        ins = A.pop() // 2
        A.insert(bisect.bisect_left(A, ins), ins)

    print(sum(A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-n for n in A]
heapq.heapify(A)

for _ in range(M):
    high = -heapq.heappop(A)
    heapq.heappush(A, -(high//2))

print(-sum(A))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

H, W = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))

ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = [list((str(input()))) for i in range(H)]


def check(h, w):
    if h < 0 or h >= H:
        return False
    if w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    return True


def main():

    map_ = [[10**10]*W for i in range(H)]
    # map_[ch][cw] = 0

    dq = deque([[ch, cw, 0]])

    while(len(dq) > 0):
        # print(dq)
        h, w, value = dq.popleft()
        map_value = map_[h][w]
        if map_value <= value:
            continue
        map_[h][w] = value

        for i in [-2, -1, 0, 1, 2]:
            for j in [-2, -1, 0, 1, 2]:
                if i == 0 and j == 0:
                    continue
                if abs(i)+abs(j) == 1:
                    if check(h+i, w+j):
                        # print(h+i, w+)
                        if map_[h+i][w+j] > value:
                            dq.appendleft([h+i, w+j, value])
                else:
                    if check(h+i, w+j):
                        if map_[h+i][w+j] > value+1:
                            dq.append([h+i, w+j, value+1])
    # for i in map_:
        # print(i)
    ans = map_[dh][dw]
    if ans == 10**10:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque

H, W = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))

ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = [list((str(input()))) for i in range(H)]


def check(h, w):
    if h < 0 or h >= H:
        return False
    if w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    return True


def main():

    map_ = [[10**10]*W for i in range(H)]
    # map_[ch][cw] = 0

    dq = deque([[ch, cw, 0]])

    while(len(dq) > 0):
        # print(dq)
        h, w, value = dq.popleft()
        map_value = map_[h][w]
        if map_value <= value:
            continue
        map_[h][w] = value

        for i in [-2, -1, 0, 1, 2]:
            for j in [-2, -1, 0, 1, 2]:
                if i == 0 and j == 0:
                    continue
                if abs(i)+abs(j) == 1:
                    if check(h+i, w+j):
                        # print(h+i, w+)
                        if map_[h+i][w+j] > value:
                            dq.appendleft([h+i, w+j, value])
                else:
                    if check(h+i, w+j):
                        if map_[h+i][w+j] > value+1:
                            dq.append([h+i, w+j, value+1])
    # for i in map_:
        # print(i)
    ans = map_[dh][dw]
    if ans == 10**10:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,x,y = map(int, input().split())
import collections

g = [[] for i in range(n)]
for i in range(n):
    if i != 0:
        g[i].append(i-1)
    if i != n-1:
        g[i].append(i+1)
g[x-1].append(y-1)
g[y-1].append(x-1)


inf = 10**5
dp = [[inf for i in range(n)] for j in range(n)]
todo = collections.deque()

for i in range(n):
    dp[i][i] = 0
    for j in g[i]:
        todo.append(j)
    while len(todo) > 0:
        now = todo.popleft()
        leng = inf
        for j in g[now]:
            if dp[i][j] == inf:
                todo.append(j)
            else:
                tem = dp[i][j] + 1
                if tem < leng:
                    leng = tem
        dp[i][now] = leng

for i in range(1,n):
    ans = 0
    for j in range(n):
        for k in range(j+1,n):
                if dp[j][k] == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

n,x,y = map(int, input().split())

ans = [0]*(n-1)
for j in range(1, n+1):
    for i in range(1, j):
        dis = min(j-i, abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))
        ans[dis-1] += 1

for i in ans:
    print(i)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))

num_count = {}
count_comb = {}
num_ans = {}

def comb2(n):
    if n not in count_comb:
        count_comb[n] = (n * (n - 1)) // 2
    return count_comb[n]

def ans(ex_num):
    if ex_num in num_ans:
        return num_ans[ex_num]

    result = 0
    for n, c in num_count.items():
        if n == ex_num:
            result += comb2(c - 1)
        else:
            result += comb2(c)
    num_ans[ex_num] = result
    return result


for a in As:
    if a not in num_count:
        num_count[a] = 0
    num_count[a] += 1

for a in As:
    print(ans(a))


### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))

num_count = {}
count_comb = {}
num_ans = {}
sum_combs = 0

def comb2(n):
    if n not in count_comb:
        count_comb[n] = (n * (n - 1)) // 2
    return count_comb[n]

def ans(ex_num):
    ex_count = num_count[ex_num]
    return sum_combs + comb2(ex_count - 1) - comb2(ex_count)
    # if ex_num in num_ans:
    #     return num_ans[ex_num]

    # result = 0
    # for n, c in num_count.items():
    #     if n == ex_num:
    #         result += comb2(c - 1)
    #     else:
    #         result += comb2(c)
    # num_ans[ex_num] = result
    # return result


for a in As:
    if a not in num_count:
        num_count[a] = 0
    num_count[a] += 1

for _, c in num_count.items():
    sum_combs += comb2(c)

for a in As:
    print(ans(a))
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

import collections
c = collections.Counter(s)
ans = []
word,count = c.most_common()[0]
ans.append(word)
for i in range(1,len(c)):
    wordi,counti = c.most_common()[i]
    if counti == count:
        ans.append(wordi)
    else:
        break
ans.sort()
print(*ans, sep = "\n")

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

import collections
c = collections.Counter(s)
ans = []
most = c.most_common()
word,count = most[0]
ans.append(word)
for i in range(1,len(c)):
    wordi,counti = most[i]
    if counti == count:
        ans.append(wordi)
    else:
        break
ans.sort()
print(*ans, sep = "\n")
### BUGGY CODE ###

h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
X = [[0 for i in range(w)] for _ in range(h)]
# M = [[] for _ in range(m)]
for i in range(m):
    mh, mw = list(map(int, input().split()))
    X[mh-1][mw-1] = 1
    # M[i] = [mh, mw]
    count_row[mh-1] += 1
    count_col[mw-1] += 1
max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
ans = max(count_row) + max(count_col) -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if X[i][j] == 0:
                ans += 1
                flag = True
                break
        if flag:
            break

# print(M)
# print(X)
# print(count_row, count_col)
# print(max_row_index, max_col_index)
print(ans)

### FIXED CODE ###

h, w, m = list(map(int, input().split()))
count_row = [0 for _ in range(h)]
count_col = [0 for _ in range(w)]
# X = [[0 for i in range(w)] for _ in range(h)]
max_col = 0
max_row = 0
max_row_index = []
max_col_index = []
M = set()
for i in range(m):
    mh, mw = list(map(int, input().split()))
    # X[mh-1][mw-1] = 1
    M.add((mh-1, mw-1))
    count_row[mh-1] += 1
    count_col[mw-1] += 1
    if count_row[mh-1] > max_row:
        max_row = count_row[mh-1]
        max_row_index = [mh-1]
    elif count_row[mh-1] == max_row:
        max_row_index.append(mh-1)
    
    if count_col[mw-1] > max_col:
        max_col = count_col[mw-1]
        max_col_index = [mw-1]
    elif count_col[mw-1] == max_col:
        max_col_index.append(mw-1)
# max_row_index = [i for i, v in enumerate(count_row) if v == max(count_row)]
# max_col_index = [i for i, v in enumerate(count_col) if v == max(count_col)]
# ans = max(count_row) + max(count_col) -1
ans = max_col + max_row -1

if len(max_col_index)*len(max_row_index) > m:
    ans += 1
else:
    flag = False
    for i in max_row_index:
        for j in max_col_index:
            if (i, j) not in M:
                ans += 1
                flag = True
                break
        if flag:
            break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import collections
import re
import copy

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	pattern = r"AC"
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		tmp = S[l-1:r]
		matchedList = re.findall(pattern, "".join(tmp))
		
		ans.append(len(matchedList))
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ptn = []
	hit = 0
	flg = False
	for i, val in enumerate(S):
		if val == "A":
			ptn.append(hit)
			if i+1 < len(S) and S[i+1] == "C":
				hit += 1
				ptn.append(hit)
				flg = True
		else:
			if flg == False:
				ptn.append(hit)
			else:
				flg = False
		
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		if l == r:
			ans.append(0)
			break
			
		tmp = ptn[r-1] - ptn[l-1]
		ans.append(tmp)
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

R,C,K=map(int,input().split())
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=map(int,input().split())
  value[r][c]=v
DP0=[[0]*(C+1) for i in range(R+1)]
DP1=[[0]*(C+1) for i in range(R+1)]
DP2=[[0]*(C+1) for i in range(R+1)]
DP3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    v=value[i][j]
    DP0[i][j]=max(DP0[i][j-1],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
    DP1[i][j]=max(DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,
                  DP3[i-1][j]+v,DP1[i][j-1],DP0[i][j-1]+v)
    DP2[i][j]=max(DP1[i][j-1]+v,DP2[i][j-1])
    DP3[i][j]=max(DP2[i][j-1]+v,DP3[i][j-1])

    
print(max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C]))

### FIXED CODE ###

R,C,K=map(int,input().split())
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=map(int,input().split())
  value[r][c]=v
DP0=[[0]*(C+1) for i in range(R+1)]
DP1=[[0]*(C+1) for i in range(R+1)]
DP2=[[0]*(C+1) for i in range(R+1)]
DP3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    v=value[i][j]
    a=DP0[i][j-1]
    b=DP1[i][j-1]
    c=DP1[i-1][j]
    d=DP2[i-1][j]
    e=DP3[i-1][j]
    f=DP2[i][j-1]
    DP0[i][j]=max(a,c,d,e)
    DP1[i][j]=max(DP0[i-1][j]+v,c+v,d+v,e+v,b,a+v)
    DP2[i][j]=max(b+v,f)
    DP3[i][j]=max(f+v,DP3[i][j-1])

print(max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C]))
### BUGGY CODE ###

import numpy as np

n = int(input())
list_a = list(map(int, input().split()))

list_a.sort()

counts = []

for i in range(0, 100000):
    if (i+1) in list_a:
        counts.append(list_a.count(i+1))
    else:
        counts.append(0)

q = int(input())
ans = sum(list_a)

for i in range(q):
    b, c = map(int, input().split())

    ans += counts[b-1] * (c - b)

    counts[c-1] += counts[b-1]
    counts[b-1] = 0

    print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())
list_a = list(map(int, input().split()))

counts = np.zeros(100000, dtype=int)

ans = 0

for i in range(len(list_a)):
    counts[list_a[i]-1] += 1
    ans += list_a[i]

q = int(input())

for i in range(q):
    b, c = map(int, input().split())

    ans += counts[b-1] * (c - b)

    counts[c-1] += counts[b-1]
    counts[b-1] = 0

    print(ans)
### BUGGY CODE ###

# coding: utf-8

n,m = map(int,input().split(" "))
q_list = []
res_list = []
for i in range(m):
    a,b = input().split(" ")
    q_list.append(int(a))
    res_list.append(b)
    


ac = 0
wa = 0
ac_list = []

for i,j in enumerate(res_list):
    if i == 0:
        if j == "AC":
            ac += 1
            ac_list.append(q_list[i])
        else:
            wa += 1
    elif q_list[i] not in ac_list:
        if j == "AC":
            ac += 1
            ac_list.append(q_list[i])
        else:
            wa += 1
    
    if len(ac_list) == n:
        break

for i,j in enumerate(res_list):
    if q_list[i] not in ac_list:
        wa -= 1



print(ac,wa)

### FIXED CODE ###

# coding: utf-8

n,m = map(int,input().split(" "))
ac_list = [0] * n
wa_list = [0] * n


wa = 0

for i in range(m):
    a,b = input().split(" ")
    if ac_list[int(a) - 1]:
        continue
    if b == "AC":
        ac_list[int(a) - 1] = 1
        wa += wa_list[int(a)-1]
    else:
        wa_list[int(a)-1] += 1
        
print(sum(ac_list),wa)
### BUGGY CODE ###

				
def factorial(number):
	if number>2:
		return number*factorial(number-1)
	elif not number==0:
		return number
	else:
		return 1
def choose2(number):
	if number>=2:
		return factorial(number)/(2*factorial(number-2))
	else:
		return 0
N = int(input())
klist = input()
k = []
for x in range(N-1):
	k.append(int(klist[:klist.index(" ")]))
	klist = klist[klist.index(" ")+1:]
k.append(int(klist))
valArr = list(set(k))
occurence = []
for i in range(len(valArr)):
	occurence.append(0)
for j in range(N):
	for x in range(len(valArr)):
		if k[j]==valArr[x]:
			occurence[x]+=1
for ball in range(len(k)):
	ans = 0
	kArray = occurence[:len(occurence)]
	for index in range(len(valArr)):
		if valArr[index]==k[ball]:
			kArray[index]-=1
			break;
	for time in kArray:
		ans+=choose2(time)
	print(int(ans))


### FIXED CODE ###

def choose2(number):
	if number>=2:
		return (number*(number-1))/2
	else:
		return 0
N = int(input())
k = list(map(int,input().split()))
valArr = list(set(k))
occurence = []
occurenceIndex = []
mx = 0
for l in k:
	if l>mx:
		mx=l
for i in range(mx+1):
	occurence.append(0)
for j in range(N):
	occurence[k[j]]+=1
	
			
'''6*5/2
5*4/2
N*(N-1)/2
(N-2)*(N-1)/2
N*(N-1)/2*(N-2)/N
occurence = [1,2,3]
ans = 0+2*1/2+3*2/2
k val = 3
correct = 0+2*1/2+2*1/2

'''
ans = 0
for time in range(len(occurence)):
	ans+=choose2(occurence[time])
for ball in range(N):
	kans = ans-choose2(occurence[k[ball]])+choose2(occurence[k[ball]]-1)
	
	print(int(kans))