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

H,W,k = map(int, input().split())
# アイテムが何処に何個あるか
fs = [[0]*(W+1) for i in range(H+1)]
for i in range(k):
    h, w, v = map(int, input().split())
    h -= 1
    w -= 1
    fs[h][w] = v

mvs = [(0,1),(1,0)]
dp = [[[-1<<50 for i in range(W+1)] for j in range(H+1)] for k in range(4)]
# dp[n][i][j] n個取ったときの、i,jにおけるアイテム価値の最大値
from collections import deque
q = deque([])
q.append((0,0))
dp[0][0][0] = 0
dp[1][0][0] = fs[0][0]
for h in range(H):
    for w in range(W):
        dp[0][h][w+1] = max(dp[0][h][w+1], dp[0][h][w])
        dp[1][h][w+1] = max(dp[1][h][w+1], dp[1][h][w], dp[0][h][w] + fs[h][w+1])
        dp[2][h][w+1] = max(dp[2][h][w+1], dp[2][h][w], dp[1][h][w] + fs[h][w+1])
        dp[3][h][w+1] = max(dp[3][h][w+1], dp[3][h][w], dp[2][h][w] + fs[h][w+1])
    for w in range(W):
        mx = 0
        for i in range(4):
            # print("fe",i,h,w,"dp",dp[i][h][w])
            mx = max(mx,dp[i][h][w])
        dp[0][h+1][w] = mx
        dp[1][h+1][w] = mx + fs[h+1][w]

H -= 1
W -= 1
ans0 = dp[0][H][W]
ans1 = dp[1][H][W]
ans2 = dp[2][H][W]
ans3 = dp[3][H][W]
# print(fs)
# for i in range(3):
#     d = dp[i]
#     for r in d:
#         print(*r)
#     print("----------")
print(max(ans1,ans2,ans3))

### FIXED CODE ###

H,W,k = map(int, input().split())
# アイテムが何処に何個あるか
fs = [[0]*(W+1) for i in range(H+1)]
for i in range(k):
    h, w, v = map(int, input().split())
    h -= 1
    w -= 1
    fs[h][w] = v

mvs = [(0,1),(1,0)]
dp = [[[-1<<50 for i in range(W+1)] for j in range(H+1)] for k in range(4)]
# dp[n][i][j] n個取ったときの、i,jにおけるアイテム価値の最大値
from collections import deque
q = deque([])
q.append((0,0))
dp[0][0][0] = 0
dp[1][0][0] = fs[0][0]
for h in range(H):
    for w in range(W):
        dp[0][h][w+1] = max(dp[0][h][w+1], dp[0][h][w])
        dp[1][h][w+1] = max(dp[1][h][w+1], dp[1][h][w], dp[0][h][w] + fs[h][w+1])
        dp[2][h][w+1] = max(dp[2][h][w+1], dp[2][h][w], dp[1][h][w] + fs[h][w+1])
        dp[3][h][w+1] = max(dp[3][h][w+1], dp[3][h][w], dp[2][h][w] + fs[h][w+1])
    for w in range(W):
        mx = 0
        for i in range(4):
            # print("fe",i,h,w,"dp",dp[i][h][w])
            mx = max(mx,dp[i][h][w])
        dp[0][h+1][w] = mx
        dp[1][h+1][w] = mx + fs[h+1][w]

H -= 1
W -= 1
ans0 = dp[0][H][W]
ans1 = dp[1][H][W]
ans2 = dp[2][H][W]
ans3 = dp[3][H][W]
# print(fs)
# for i in range(3):
#     d = dp[i]
#     for r in d:
#         print(*r)
#     print("----------")
print(max(ans1,ans2,ans3))
### BUGGY CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [0.0] * n
for i in range(n):
    e[i] = (1 + p[i]) * 0.5
s = [0.0] * (n - k + 1)
for i in range(n - k + 1):
    for j in range(k):
        s[i] += e[i + j]
print(max(s))


### FIXED CODE ###

n, k = map(int, input().split(" "))
p = list(map(int, input().split(" ")))
e = [(1 + p[i]) * 0.5 for i in range(n)]
s = 0.0
for i in e[:k]:
    s += i
t = s
for i in range(n - k):
    t = t - e[i] + e[k + i]
    s = max(s, t)
print(s)
### BUGGY CODE ###

a, b, k = map(int, input().split())
temp = 0
ans = [i for i in range(a, b + 1)]

for i in sorted(list(set(ans[:k]) | set(ans[-k:]))):
  print(i) 

### FIXED CODE ###

a, b, k = map(int, input().split())

cnt = 0
if b - a + 1>= 2 * k:
  for i in range(a, a + k):
    print(i)
  for i in range(b - k + 1, b + 1):
    print(i)
else:
  for i in range(a, b + 1):
    print(i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
sum = 0
# temp1 = 0
# temp2 = 0
MOD = 1000000007
for i in range(0, N-1):
    for j in range(i+1, N):
        #print(i, j)
        temp1 = 0
        temp2 = 0
        temp3 = 0
        temp1 = A[i] % MOD
        temp2 = A[j] % MOD
        temp3 = temp1 * temp2
        sum = (sum + temp3) % MOD
#sum = sum % MOD
print(sum)

### FIXED CODE ###

MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
ans = 0
B = [0]*(N-1)
sumA = sum(A)
for i in range(1, N):
    sumA -= A[i-1]
    B[i-1] = sumA
for i in range(0, N-1):
    ans += A[i] * B[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

import itertools

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
for y in range(H):
    Hor[y] = aaa(S[y])

Ver = [0]*W
for x in range(W):
    Ver[x] = aaa([S[_][x] for _ in range(H)])

ans = 1
for x,y in itertools.product(range(W),range(H)):
    h = Hor[y][x]
    v = Ver[x][y]
    ans = max(ans,h+v-1)

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [0]*H
for i in range(H):
    S[i] = list(input())

def aaa(s):
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o += [n] * n
        else:
            o += [0]
            i += 1
    return o

Hor = [0]*H
y = 0
while y != H:
    Hor[y] = aaa(S[y])
    y += 1

Ver = [0]*W
x = 0
while x != W:
    _ = 0
    s = [0] * H
    while _ != H:
        s[_] = S[_][x]
        _ += 1
    Ver[x] = aaa(s)
    x += 1

ans = 1
x = 0
while x != W:
    y = 0
    while y != H:
        h = Hor[y][x]
        if h:
            v = Ver[x][y]
            ans = max(ans,h+v-1)
        y += 1
    x += 1

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

import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
for _ in range(M):
    B, C = map(int,input().split())
    A.sort()
    if A[B - 1] <= C:
        A[:B] = [C] * B 
    else:
        A = np.maximum(A, C)
print(np.sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(N):
    if A[i] >= BC[j][1]:
        break
    else:
        A[i] = BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j += 1
        if j >= M:
            break
print(sum(A))
### BUGGY CODE ###

#!/usr/bin/env python3
import math

primes = [-1 for i in range(100000)]

def is_prime(x):
    global primes

    if primes[x] != -1:
        return primes[x] == 1

    if x < 2:
        primes[x] = 0
        return False
    if x == 2 or x == 3 or x == 5:
        primes[x] = 1
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        primes[x] = 0
        return False

    sx = math.sqrt(x)
    prime = 7
    step = 4
    while prime <= sx:
        if x % prime == 0:
            primes[x] = 0
            return False

        prime += step
        step = 6 - step

    primes[x] = 1
    return True

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

#    r_max = 100000
#    primes = [True for i in range(r_max)]
#    primes[0] = False
#    primes[1] = False
#    i = 2
#    max_i = int(math.sqrt(r_max))
#    while i <= max_i:
#        for j in range(i * i, r_max, i):
#            primes[j] = False
#        while i <= max_i:
#            i += 1
#            if primes[i]:
#                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if is_prime(j) and is_prime(int((j + 1) / 2)):
                c += 1
        print(c)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

    r_max = 100000
    primes = [True for i in range(r_max)]
    like_numbers = [0 for i in range(r_max)]

    primes[0] = primes[1] = False
    max_i = int(math.sqrt(r_max))
    i = 2
    while i <= max_i:
        primes[i] = True
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(3, r_max, 2):
        if primes[i] and primes[int((i + 1) / 2)]:
            like_numbers[i] = 1

    c = 0
    for i in range(3, r_max, 2):
        if like_numbers[i]:
            c += 1
        like_numbers[i] = c


    for i in range(Q):
        if l[i] == 1:
            print(like_numbers[r[i]])
        else:
            print(like_numbers[r[i]] - like_numbers[l[i] - 2])

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

t = input()
l = []
for i in t:
    l.append(i)


for i in range(len(l)):
    if t[i] == "?":
        l[i] = "D"
ans = ""
for i in l:
    ans += i

print(ans)

### FIXED CODE ###

t = input()

print(t.replace("?", "D"))
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [float('inf') for i in range(n)]
    dp[0] = 0
    for i in range(1,n):
        for j in range(1,k+1):
            if i-j<0:
                break
            m = dp[i-j] + abs(h[i]-h[i-j])
            if dp[i]>m:
                dp[i] = m
    print(dp[n-1])
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [float('inf') for i in range(n)]
    dp[0] = 0
    for i in range(1,n):
        for j in range(1,min(i+1,k+1)):
            m = dp[i-j] + abs(h[i]-h[i-j])
            if dp[i]>m:
                dp[i] = m
    print(dp[n-1])
    

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

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))


    def check(n ,x, m):
        _d = [val % m for val in d]

        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest = 0 if n_rest == 0 else sum(_d[:n_rest])
        a_last = x + n_d * sum(_d) + _d_rest
        n_step = a_last // m
        # n_same
        d0_rest = 0 if n_rest == 0 else _d[:n_rest].count(0)
        n_same = n_d * _d.count(0) + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(check(n, x, m))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
import numpy as np
def run():
    k,q = map(int, sysread().split())
    d = list(map(int,sysread().split()))
    d = np.array(d, dtype=np.uint64)

    def check(n ,x, m):
        _d = d % m
        d0 = d % m == 0
        # n_step
        n_d = (n-1) // k
        n_rest = (n-1) % k
        x %= m
        _d_rest, d0_rest = 0, 0
        if n_rest != 0:
            _d_rest = _d[:n_rest].sum()
            d0_rest = d0[:n_rest].sum()

        a_last = x + n_d * _d.sum() + _d_rest
        n_step = a_last // m
        # n_same
        n_same = n_d * d0.sum() + d0_rest

        return n-1 - n_same - n_step


    for _ in range(q):
        n,x,m = map(int, sysread().split())
        print(int(check(n, x, m)))

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

import sys, fractions
input = sys.stdin.readline

N = int(input())
A = [int(i) for i in input().split()]
ans = 0

for i in range(N):
  a = A.pop(0)
  tmp = A[0]
  for j in range(1,N-1):
    tmp = fractions.gcd(tmp, A[j])
  ans = max(ans, tmp)
  A.append(a)
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1

def gcd(m, n):
  x = max(m, n)
  y = min(m, n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x % y
      x = y
      y = z
    else:
      return z

L, R = {}, {}
for i in range(N):
  if i == 0:
    L[0] = A[0]
    R[N-(i+1)] = A[N-(i+1)]
  else:
    L[i] = gcd(L[i-1], A[i])
    R[N-(i+1)] = gcd(R[N-i], A[N-(i+1)])

for i in range(N):
  if i == 0:
    tmp = R[1]
  elif i == N-1:
    tmp = L[N-2]
  else:
    tmp = gcd(L[i-1], R[i+1])
  ans = max(tmp, ans)

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

from sys import stdin

def move(line, kids):
  for index in range(len(line)):
    if line[kids[index]] == "R":
      kids[index] += 1
    else:
      kids[index] -= 1
  return kids

line = stdin.readline()
len_line = len(line)
kids = [i for i in range(len_line)]
for i in range(10**100):
  kids = move(line, kids)

ans = [0 for i in range(len_line)]
for i in range(len_line):
  ans[kids[i]]+=1
  
print(" ".join(map(str,ans)))


### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    s = input()
    ans = [1 for _ in range(len(s))]
    for i in range(len(s)-2):
        if s[i] == 'R' and s[i+1] == 'R':
            ans[i+2] += ans[i]
            ans[i] = 0
    for i in range(len(s)-1, 1, -1):
        if s[i] == 'L' and s[i-1] == 'L':
            ans[i-2] += ans[i]
            ans[i] = 0
    print(" ".join(map(str, ans)))



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

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9997
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import copy

data = input().split()
N = int(data[0])
K = int(data[1])

TL = input()
TL = list(TL)
TLlist = []
now = TL[0]
nowlist = now

for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)

maxS = 0
cnt = 0
fg = 0
tfg = 0
fg2 = False
loplist = copy.deepcopy(TLlist)

for lop3 in range(len(loplist)):
    for lop2 in range(len(loplist)):
        if loplist[lop2][:1] == "0":
            if fg <= tfg:
                num = len(loplist[lop2])
                loplist[lop2] = ""
                for lop3 in range( num ):
                    loplist[lop2] += "1"
                cnt += 1
                if cnt == K:
                    fg2 = True
                    break
            else:
                tfg += 1
    loplist = "".join(loplist).split("0")
    for lop2 in loplist:
        if maxS < len(lop2):
            maxS = len(lop2)

    loplist = copy.deepcopy(TLlist)
    fg += 1
    cnt = 0
    tfg = 0
    if fg2 == False:
        break
    else:
        fg2 == False

print(maxS)


### FIXED CODE ###

data = input().split()
N = int(data[0])
K = int(data[1])
 
TL = list(input())
TLlist = []
TLLlist = []
now = TL[0]
nowlist = now
anslist = []
 
for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)
TLLlist.append(len(nowlist))
 
 
if TLlist[0][:1] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    anslist.append( sum(TLLlist[1:2*K + 2]) )
    for lop in range(3,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
elif TLlist[0][:1] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    for lop in range(2,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
 
print(max(anslist))
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())


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

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


p = []
p_equal = []
for x in range(1, 100):
    for y in range(1, 100):
        if x + y > 100:
            break
        for z in range(1, 100):
            if x + y + z > 100:
                break
            #         p.append((x, y, z))
            if x == y == z:
                p_equal.append(calc(x, y, z))
            else:
                p.append(calc(x, y, z))

# print(p)

for i in range(1, N + 1):
    if i in p_equal:
        print(1)
    elif i in p:
        print(3)
    else:
        print(0)


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections
from numba import jit

N = int(input())

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

@jit(cache=True)
def calc(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


res = [0] * 1000009

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = calc(x, y, z)
            res[n - 1] += 1

for i in range(N):
    print(res[i])
### BUGGY CODE ###

def gcd(a, b):
    x, y = [a, b] if a > b else [b, a]
    while y:
        x, y = y, x%y
    return x

a, b = list(map(int, input().split(' ')))
c = gcd(a, b)
a, b = a//c, b//c

x = 0
y = None
while True:
    tmp = (1-a*x)/b
    if tmp == int(tmp):
        y = int(tmp)
        break
        
    x *= -1
    tmp = (1-a*x)/b
    if tmp == int(tmp):
        y = int(tmp)
        break
    x *= -1
    x += 1

print(x, y)


### FIXED CODE ###

def gcd(a, b):
    x, y = [a, b] if a > b else [b, a]
    while y:
        x, y = y, x%y
    return x

def solve(a, b):
    if b == 1:
        return 0, 1
    elif a == 1:
        return 1, 0

    A, B, Q, R = [a], [b], [b//a], [b%a]
    i = 0
    while R[i] != 0:
        B.append(A[i])
        A.append(R[i])
        Q.append(B[i+1]//A[i+1])
        R.append(B[i+1]%A[i+1])
        i += 1

    x, y = -1*Q[len(Q)-2], 1
    for i in range(len(A)-3, -1, -1):
        x, y = y - x*Q[i], x

    return x, y

a, b = list(map(int, input().split(' ')))
c = gcd(a, b)
a, b = a//c, b//c

x, y = solve(a,b)
print(x, y)
### BUGGY CODE ###

n,m=map(int,input().split())
f=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
g=[0]*(n+1)
p=[0]*(n+1)
for i in range(1,n+1):
    if p[i]==0:
        p[i]=i
        data=[i]
        while len(data)>0:
            pos=data.pop(0)
            p[pos]=i
            for j in f[pos]:
                if p[j]==0:
                    data.append(j)
for i in range(n):
    g[p[i+1]]+=1
print(max(g))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
root=[-1]*n
def r(x):
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]
def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i))
print(ans)
### BUGGY CODE ###

N,X,*S=map(int,open(0).read().split())
e=enumerate
d=range(X+1)
for i,s in e(sorted(S)):x=d;d=[t*i+x[j%s]for j,t in e(x)]
print(d[-1]%(10**9+7))

### FIXED CODE ###

N,X,*S=map(int,open(0).read().split())
e=enumerate
d=range(X+1)
for i,s in e(sorted(S)):d=[(t*i+d[j%s])%(10**9+7)for j,t in e(d)]
print(d[-1])
### BUGGY CODE ###

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

cnt = 0
flag = True

for i in range(N):
  flag = True
  P_i = P[i]
  for j in range(i + 1):
    if P_i > P[j]:
      flag = False
  if flag:
    cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 1
min = P[0]
flag = True

for i in range(1, N):
  if P[i] <= min:
    cnt += 1
    min = P[i]
    

print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))

query = []
for _ in range(q):
    query.append(list(map(int, input().split())))

for n, x, m in query:
    l = []
    for i in range(k):
        l.append(d[i]%m)
    zero = l.count(0)
    total = x%m
    total += sum(l)*((n-1)//k)
    zero_total = zero*((n-1)//k)

    s = n
    n -= 1
    n -= n//k * k
    for i in range(n):
        total += l[i]

    for i in range(n):
        if l[i] == 0:
            zero_total += 1

    print(s-1-total//m-zero_total)


### FIXED CODE ###

import sys
input = sys.stdin.readline
k, q = map(int, input().split())
d = list(map(int, input().split()))
query = [None]*q
for i in range(q):
    query[i] = list(map(int, input().split()))

def answer_query(n, x, m):
    l = [m if i%m == 0 else i%m for i in d]
    count = n // k
    rem = n % k
    s = sum(l)
    total = s%m * count + x%m
    for i in range(rem):
        total += l[i]

    total //= m
    total += s//m * count

    print(n-total)


for n, x, m in query:
    answer_query(n-1, x, m)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A_set = list(set(A))
Ad = {a_set: A.count(a_set) for a_set in A_set}
score_sum = sum([(x>1) * x * (x-1) / 2 for x in list(Ad.values())])
Ad_score = {ad_key: score_sum - (ad_value -1) * (ad_value > 0) for ad_key, ad_value in Ad.items()}
A_out = [str(int(Ad_score[a])) for a in A]

print('\n'.join(A_out))


### FIXED CODE ###

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

# A_set = list(set(A))
# Ad = {a_set:A.count(a_set) for a_set in A_set}
Ad = {}
for i in A:
  if not i in Ad:
    Ad[i]=0
  Ad[i] += 1

score_sum = sum([x*(x-1)/2 for x in list(Ad.values())])

for a in A:
    print(int(score_sum - (Ad[a] - 1)))