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

N, C = map(int, input().split())
dic = [[] for _ in range(C + 1)]
for _ in range(N):
    s, t, c = map(int, input().split())
    dic[c].append([s, t])
for c in range(C + 1):
    dic[c] = sorted(dic[c])
    l = len(dic[c])
    i = 0
    while i < l - 1:
        if i < l - 1 and dic[c][i][1] == dic[c][i + 1][0]:
            dic[c][i + 1][0] = dic[c][i][0]
            dic[c].pop(i)
            l -= 1
        else:
            i += 1
f = [0 for _ in range(100002)]
for c in range(C + 1):
    for t in dic[c]:
        f[t[0]] += 1
        f[t[1] + 1] -= 1

ans = 0
for i in range(1, 100001):
    f[i] += f[i - 1]
    if ans < f[i]:
        ans = f[i]
print(ans)

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N, C = map(int, input().split())
    dic = [[] for _ in range(C + 1)]
    for _ in range(N):
        s, t, c = input().split()
        dic[int(c)].append([int(s), int(t)])
    for c in range(C + 1):
        l = len(dic[c])
        if l == 1:
            continue
        dic[c] = sorted(dic[c])
        i = 0
        while i < l - 1:
            if i < l - 1 and dic[c][i][1] == dic[c][i + 1][0]:
                dic[c][i + 1][0] += 1
            else:
                i += 1
    f = [0 for _ in range(100002)]
    for c in range(C + 1):
        for t in dic[c]:
            f[t[0]] += 1
            f[t[1] + 1] -= 1
    ans = 0
    for i in range(1, 100001):
        f[i] += f[i - 1]
        if ans < f[i]:
            ans = f[i]
    print(ans)

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

from itertools import accumulate
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


a = accumulate(A)
C = Counter(a)
max_v = max(C.values())
f = [1]*(max_v+1)


def fact(n):
    for i in range(1, n):
        f[i+1] = f[i]*(i+1)


fact(max_v)


def comb(n, r):
    return f[n]//(f[r]*f[n-r])


ans = 0
for i, v in C.items():
    if i == 0:
        ans += v
    if v > 1:
        ans += comb(v, 2)
print(ans)


### FIXED CODE ###

from itertools import accumulate
from collections import Counter
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


a = accumulate(A)
C = Counter(a)


def comb(v):
    return (v)*(v-1)//2


ans = 0
for i, v in C.items():
    if i == 0:
        ans += v
    if v > 1:
        ans += comb(v)
print(ans)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())

graph = [[] for _ in range(n)]
d = [[float("inf")]*n for i in range(n)]

for i in range(n):
    s = input()
    for j, sj in enumerate(s):
        d[i][i] = 1
        if sj == '1':
            graph[i].append(j)
            d[i][j] = 1
            d[j][i] = 1

colors = [0 for i in range(n)]

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to in graph[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    return True

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

def warshall_floyd(d, M):
    for k in range(M):
        for i in range(M):
            for j in range(M):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

##############################


if is_bipartite():
    ret = 0
    for a in warshall_floyd(d,n):
        ret = max(ret, max(a))
    print(ret+1)
else:
    print(-1)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())

graph = [[] for _ in range(n)]
d = [[float("inf")]*n for i in range(n)]

for i in range(n):
    s = input()
    for j, sj in enumerate(s):
        d[i][i] = 1
        if sj == '1':
            graph[i].append(j)
            d[i][j] = 1
            d[j][i] = 1

colors = [0 for i in range(n)]

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    stack = [(0,1)] # (頂点、色)のタプルをスタックする。最初は(頂点0, 黒(1))
    while stack:
        #スタックから最後に追加された(頂点, 色)をpop
        v,color = stack.pop()
        #今いる点を着色
        colors[v] = color
        #今の頂点から行けるところをチェック
        for to in graph[v]:
            #同じ色が隣接してしまったらFalse
            if colors[to] == color:
                return False
            #未着色の頂点があったら反転した色と共にスタックに積む
            if colors[to] == 0:
                stack.append((to, -color))
    #調べ終わったら矛盾がないのでTrue
    return True

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

def warshall_floyd(d, M):
    for k in range(M):
        for i in range(M):
            for j in range(M):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

##############################


if is_bipartite():
    ret = 0
    for a in warshall_floyd(d,n):
        ret = max(ret, max(a))
    print(ret+1)
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
a=[-1]*(N+1)
b=[[] for i in range(N+1)]
for i in range(1,N+1):
  a[i]=int(input())
  b[a[i]].append(i)

prev=[2]  
count=0
button=2
while(button!=1):
  if len(b[button]) != 0:
    button = b[button].pop()
    if button not in prev:
      prev.append(button)
    else:
      button=prev[-1]
  else:
    if prev[-1]==button:
      prev.pop()
      if len(prev) == 0:
        print(-1)
        exit(0)
      button = prev[-1]
      continue
  
print(len(prev) - 1)

### FIXED CODE ###

N=int(input())
a=[-1]*(N+1)
for i in range(1,N+1):
  a[i]=int(input())
pos = 1
ans = 0
for _ in range(N):
  if pos == 2:
    print(ans)
    exit(0)
  pos = a[pos]
  ans += 1
  

print(- 1)
### BUGGY CODE ###

def check(s, t, a, b, c, d):
    ssum = 0
    tsum = 0
    for i in range(a - 1, b):
        if s[i] == 'A':
            ssum += 1
        else:
            ssum += 2 
    for i in range(c - 1, d):
        if t[i] == 'A':
            tsum += 1
        else:
            tsum += 2 
    return (ssum - tsum) % 3 == 0

s = input()
t = input()
q = int(input())
a = [[int(i) for i in input().split()] for j in range(q)]

for i in range(q):
    if check(s, t, a[i][0], a[i][1], a[i][2], a[i][3]):
        print('YES')
    else:
        print('NO')


### FIXED CODE ###

def check(ssum, tsum, a, b, c, d):
    return ((ssum[b] - ssum[a - 1]) - (tsum[d] - tsum[c - 1])) % 3 == 0

s = input()
t = input()
q = int(input())
a = [[int(i) for i in input().split()] for j in range(q)]

ssum = [0]
tsum = [0]
for i in range(len(s)):
    if s[i] == 'A':
        temp = 1
    else:
        temp = 2
    ssum.append(ssum[i] + temp)
for i in range(len(t)):
    if t[i] == 'A':
        temp = 1
    else:
        temp = 2
    tsum.append(tsum[i] + temp)

for i in range(q):
    if check(ssum, tsum, a[i][0], a[i][1], a[i][2], a[i][3]):
        print('YES')
    else:
        print('NO')
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline

def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')



### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()
d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')
### BUGGY CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))

dp = [-1]*(n+1)
dp[0] = 0

for i in range(n-1):
  for j in range(1,k+1):
    if i+j==n:
      break
    if dp[i+j] == -1:
      dp[i+j] = dp[i] + abs(h[i]-h[i+j])
    else:
      dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
  
print(dp[n-1])

### FIXED CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*(n)
dp[0] = 0

for i in range(1, n):
  j = max(0, i-k)
  dp[i] = min([dpk + abs(h[i]-hk) for dpk, hk in zip(dp[j:i], h[j:i])])
  
print(dp[n-1])
### BUGGY CODE ###

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

if N > K:
    ans = 0
    while K > 0:
        ans = A[ans] -1
        K -= 1
    print(ans+1)
else:
    count = 0
    a = 0
    visited = [0]
    while True:
        a = A[a]-1
        count += 1
        if a in visited:
            break
        visited.append(a)
    before_roop = visited.index(a)
    cycle = len(visited) - before_roop
    mod = (K - before_roop)%cycle
    print(visited[before_roop + mod] +1)


### FIXED CODE ###

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

if N > K:
    ans = 0
    while K > 0:
        ans = A[ans] -1
        K -= 1
    print(ans+1)
else:
    count = 0
    a = 0
    # visited = [0]
    is_visited = [0 for _ in range(N)]
    is_visited[0] = 1
    while True:
        a = A[a]-1
        count += 1
        if is_visited[a] > 0:
            before_roop = is_visited[a]-1
            cycle = count - before_roop
            break
        is_visited[a] = count+1
        # if a in visited:
        #     break
        # visited.append(a)
    # before_roop = visited.index(a)
    # cycle = len(visited) - before_roop
    mod = (K - before_roop)%cycle
    # print(visited[before_roop + mod] +1)
    print(is_visited.index(is_visited[a] +mod) +1)
### BUGGY CODE ###

def main():
    import heapq
    n, m, *abc = map(int, open(0).read().split())
    a = abc[:n]
    heapq.heapify(a)
    *bc, = zip(*[iter(abc[n:])] * 2)

    for b, c in bc:
        for i in range(b):
            heapq.heappush(a, c)

    s = heapq.nlargest(n, a)
    print(sum(s))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

divmemo = {}
def popcountdiv(n, onecount):
    if n in divmemo:
        return divmemo[n]
    myonecount = onecount
    if myonecount == -1:
        myonecount = bin(n).count("1")
    res = n % myonecount
    divmemo[n] = res
    return res

memo = {}
def f(n, onecount):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    else:
        res = f(popcountdiv(n, onecount), -1)
        memo[n] = res+1
        return 1 + res

N = int(input())
X = input()
onecount = X.count("1")
mathX = int(X, 2)
for i in range(N):
    if X[i] == "1":
        #print(X, mathX, mathX-2**(N-(i+1)))
        print(f(mathX-2**(N-(i+1)), onecount-1))
    else:
        #print(X, mathX, mathX+2**(N-(i+1)))
        print(f(mathX+2**(N-(i+1)), onecount+1))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

S = list(input())
u = 10**9+7
d = len(S)
dp = [0]*13
dp[0] = 1
m = 1

for i in range(d-1,-1,-1):
    tmp = [0]*13
    a = S[i]
    if a=='?':
        for j in range(10):
            c = j*m
            for k in range(13):
                tmp[(c+k)%13] += dp[k]
                tmp[(c+k)%13] %= u
    else:
        c = int(a)*m
        for k in range(13):
            tmp[(c+k)%13] += dp[k]
            tmp[(c+k)%13] %= u
    m *= 10
    m %= 13
    dp = tmp[:]
print(dp[5])

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
S = list(input())
u = 10**9+7
d = len(S)
dp = [0]*13
dp[0] = 1
m = 1

for i in range(d-1,-1,-1):
    tmp = [0]*13
    a = S[i]
    if a=='?':
        for j in range(10):
            c = j*m
            for k in range(13):
                n = (c+k)%13
                tmp[n] += dp[k]
                tmp[n] %= u
    else:
        c = int(a)*m
        for k in range(13):
            n = (c+k)%13
            tmp[n] += dp[k]
            tmp[n] %= u
    m *= 10
    m %= 13
    dp = tmp
print(dp[5])
### BUGGY CODE ###

y = 0
x = []
new = []
things = int(input())

for i in range(things):
    p = input()
    x.append(p)
for i in x:
    if i not in new:
        new.append(i)

print(len(new))

### FIXED CODE ###

s = set([])
things = int(input())

for i in range(things):
    p = input()
    s.add(p)

print(len(s))
### BUGGY CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    rmky = [set() for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = (l-1, r-1)
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
        if r < n:
            rmky[r].add(ky)
    for i in range(1, n):
        dics[i].update(dics[i-1])
        for v in rmky[i]:
            dics[i].pop(v)
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if v > dist[p]:
            continue
        if p == n-1:
            break
        for l, r in dics[p].keys():
            if dist[r] > v + dics[p][(l, r)]:
                heapq.heappush(hq, [v + dics[p][(l, r)], r])
            for i in reversed(range(l, r+1)):
                if dist[i] > v + dics[p][(l, r)]:
                    dist[i] = v + dics[p][(l, r)]
                else:
                    break
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import heapq

def main():
    n, m = map(int, input().split())
    dics = [{} for _ in range(n)]
    for _ in range(m):
        l, r, c = map(int, input().split())
        ky = r-1
        if ky in dics[l-1]:
            if c < dics[l-1][ky]:
                dics[l-1][ky] = c
        else:
            dics[l-1][ky] = c
    dist = [float("inf")]*n
    dist[0] = 0
    hq = []
    heapq.heappush(hq, [0, 0])
    idx = 0
    while len(hq) > 0:
        v, p = heapq.heappop(hq)
        if p < idx:
            continue
        if p == n-1:
            break
        for i in range(idx+1, p):
            if len(dics[i]) > 0:
                for ky in dics[i].keys():
                    if ky in dics[p]:
                        if dics[p][ky] > dics[i][ky]:
                            dics[p][ky] = dics[i][ky]
                    else:
                        if p < ky:
                            dics[p][ky] = dics[i][ky]
        idx = p
        for r in dics[p].keys():
            if dist[r] > v + dics[p][r]:
                dist[r] = v + dics[p][r]
                heapq.heappush(hq, [v + dics[p][r], r])
    if dist[n-1] == float("inf"):
        print(-1)
    else:
        print(dist[n-1])

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

a, b, x = map(int, input().split())
count_a = 0
count_b = 0
for i in range(a):
    if i%x == 0:
        count_a+=1

for i in range(b+1):
    if i%x == 0:
        count_b+=1

print(count_b-count_a)

### FIXED CODE ###

a, b, x = map(int, input().split())
print(b//x - (a-1)//x)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = tuple([[0] * (n + 1) for _ in range(m + 1)])

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            else:
                count_list[i][j] = max(count_list[i - 1][j], count_list[i][j - 1])

    return count_list[m][n]


def lcs_better(A, B):
    cost_history = [None]
    for ele in B:
        for index in range(len(cost_history) - 1, -1, -1):
            # ???????¬??????°????????????????§???¨A??\?????°??????(ele), ????????°?????????
            found = A.find(ele, cost_history[index])
            if found != -1:
                if index + 1 < len(cost_history):
                    cost_history[index + 1] = min(cost_history[index + 1], found + 1)
                # ??¨???????????°?????¢?????°?????¶?????°????????´???
                else:
                    # assert index + 1 == len(cost_history)
                    cost_history.append(found + 1)

    return len(cost_history) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

import sys
input= sys.stdin.readline
N, M = map(int,input().split())

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

A.sort(reverse=True)
cnt = 1
A[0]=A[0]//2

if N==1:
    while A[0]>0 and cnt<M:
        cnt+=1
        A[0]=A[0]//2
else:
    while cnt<M:
        while A[0]>=A[1] and cnt<M:
            cnt+=1
            A[0]=A[0]//2
          
        b=A[0]
        A.sort(reverse=True)
    
print(sum(A))
    
        

### FIXED CODE ###

import heapq

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

a = [-int(x) for x in input().split()]

heapq.heapify(a)

num = 0
hq = 1

while num < M and hq != 0:
    hq = -heapq.heappop(a)
    hq2 = hq // 2
    heapq.heappush(a, -hq2)
    num += 1

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

n = int(input())
goods =[]
for i in range(n):
    goods.append(input())
    goods = list(set(goods))
print(len(goods))

### FIXED CODE ###

n = int(input())
goods =[]
for i in range(n):
    goods.append(input())
goods = list(set(goods))
print(len(goods))
### BUGGY CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N, K = map(int, input().split())
A = list(input().split())
B = set(A)
L = []
for i in B:
    L.append(A.count(i))
L.sort()
if len(B) <= K:
    print('0')
else:
    print(str(sum(L[0:len(B)-K])))


### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = set(A)
    L = [0 for i in range(N+1)]
    for i in A:
        L[i] += 1
    L.sort()
    if len(B) <= K:
        print('0')
    else:
        print(str(sum(L[0:N+1-K])))


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

n,x,y = map(int, input().split())
dst = [[0]*n]*n
ans = [0]*n

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

for m in range(1,n):
    print(ans[m]//2)

### FIXED CODE ###

n,x,y = map(int, input().split())
ans = [0]*(n-1)

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

for m in range(n-1):
    print(ans[m])
### BUGGY CODE ###

N, Q =map(int,input().split())
S =input()
LR = [list(map(int,input().split())) for i in range(Q)]
isACinit =[0]*N
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        isACinit[i] = 1
#ans = [0]*Q
#print(isACinit)
for i in range(Q):
#    ans[i] = sum(isACinit[LR[i][0]:LR[i][1]])
    print(sum(isACinit[LR[i][0]-1:LR[i][1]-1]))

### FIXED CODE ###

N, Q =map(int,input().split())
S =input()
LR = [list(map(int,input().split())) for i in range(Q)]
ACnum =[0]*(N+1)
Sofar = 0
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        Sofar+=1
    ACnum[i+1] = Sofar
ACnum[N]=Sofar
#print(ACnum)
for i in range(Q):
    print(ACnum[LR[i][1]-1]-ACnum[LR[i][0]-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
if a_first == a_second:
    for i in range(n):
        print(a_first)
else:
    for i in range(n):
        if i == a.index(a_first):
            print(a_second)
        else:
            print(a_first)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
for i in a:
    print(a_second if i == a_first else a_first)
### BUGGY CODE ###

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans_hash = {}
    num_hash = {}
    for n in A:
        if n not in ans_hash:
            ans = 0
            a = A[:]
            i = a.index(n)
            del a[i]
            val = Counter(a).values()
            for num in val:
                if num in num_hash:
                    ans += num_hash[num]
                else:
                    num_hash[num] = num * (num - 1) // 2
                    ans += num_hash[num]
            ans_hash[n] = ans
        print(ans_hash[n])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

def choose(n):
    return n * (n - 1) // 2


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    cnt = 0
    for c in C.values():
        cnt += choose(c)

    for a in A:
        ans = cnt
        ans -= choose(C[a])
        ans += choose(C[a] - 1)
        print(ans)


if __name__ == '__main__':
    main()