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

class Node:
	elm = None
	next = None
	prev = None

class MyList:
	head = tail = None

	def insert(self, x):
		if self.head == None:
			self.head = self.tail = Node()
			self.head.elm = x
		else:
			n = Node()
			n.elm = x
			n.next = self.head
			self.head.prev = n
			self.head = n

	def delete(self, x):
		n = self.head
		while n and n.elm!=x:
			n = n.next
		self.__delete_node(n)

	def deleteFirst(self):
		self.__delete_node(self.head)

	def deleteLast(self):
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == None: 
			return
		if n == self.head:
			self.head = n.next
		if n == self.tail:
			self.tail = n.prev
		if n.prev:
			n.prev.next = n.next
		if n.next:
			n.next.prev = n.prev

	def __traverse(self):
		n = self.head
		while n:
			yield n.elm
			n = n.next

	def __str__(self):
		return " ".join([str(s) for s in self.__traverse()])

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(int(line[7:]))
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(int(line[7:]))
print myList

### FIXED CODE ###

class MyList:
	head = tail = None

	def insert(self, x):
		n = [x, None, None]
		if self.head == None:
			self.head = self.tail = n
		else:
			n[2] = self.head
			self.head[1] = n
			self.head = n

	def delete(self, x):
		n = self.head
		while n and n[0] != x:
			n = n[2]
		if n: 
			self.__delete_node(n)

	def deleteFirst(self):
		self.__delete_node(self.head)

	def deleteLast(self):
		self.__delete_node(self.tail)

	def __delete_node(self, n):
		if n == self.head:
			self.head = n[2]
		if n == self.tail:
			self.tail = n[1]
		if n[1]:
			n[1][2] = n[2]
		if n[2]:
			n[2][1] = n[1]

	def print_all(self):
		n = self.head
		while n:
			print n[0],
			n = n[2]

myList = MyList()
n = int(raw_input())
for _ in xrange(n):
	line = raw_input()
	if line[0]=='i':
		myList.insert(line[7:])
	elif line[6]=='F':
		myList.deleteFirst()
	elif line[6]=='L':
		myList.deleteLast()
	else:
		myList.delete(line[7:])
myList.print_all()
### BUGGY CODE ###

L, R = map(int, input().split())

res = []
for i in range(L, R+1):
    for j in range(i+1, R+1):
        res.append((i*j) % 2019)
print(min(res))

### FIXED CODE ###

L, R = map(int, input().split())

MOD = 2019

res = []
for i in range(L, min(L+MOD, R+1)):
    for j in range(i+1, min(L+MOD, R+1)):
        res.append((i*j) % MOD)
print(min(res))
### BUGGY CODE ###

k, n = map(int, input().split())
A = list(map(int, input().split()))
ans = [0]*n
B = [0]*n

for j in range(n):
    for i in range(n):
        B[i] = A[i] - A[j]
        if abs(B[i]) >= k/2:
            B[i] = abs(B[i]) - k
    B.sort()
    #print(B)
    ans[j] = B[n-1] - B[0]
print(min(ans))

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
A_list =[]
for i in range(n-1):
    A_list.append(a[i+1]-a[i])

A_list.append(a[0] + (k - a[n-1]))
print(k - max(A_list))
### BUGGY CODE ###

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
import sys
sys.setrecursionlimit(2000000)
N = int(input())
AB = [{}for _ in range(N+1)]
for i in range(N-1):
    a,b,c = map(int,input().split())
    AB[a][b] = c
    AB[b][a] = c

Q,K = map(int,input().split())

path = {K:""}
dp = [0]*(N+1)
def dfs(n,cost):
    path[n]=""
    dp[n]=cost
    for i,c in AB[n].items():
        if i not in path:
            dfs(i,cost+c)
dfs(K,0)
for i in range(Q):
    x,y=map(int,input().split())
    print(dp[x]+dp[y])

### FIXED CODE ###

"""
--- アルゴリズム概要 ---
前計算で頂点Kから各ノードへの最短路を記録しておき、
各クエリに対しては、dp[a]+dp[b]を返せばよい。

頂点Kから各ノードへの最短ルートはdfsとかで記録していけばよい。
"""
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(20000000)
    input = sys.stdin.readline
    N = int(input())
    AB = [[]for _ in range(N+1)]
    for i in range(N-1):
        a,b,c = map(int,input().split())
        AB[a].append((b,c))
        AB[b].append((a,c))

    Q,K = map(int,input().split())

    path = {K:""}
    dp = [0]*(N+1)
    que = deque()
    for n,c in AB[K]:
        que.append((n,c))
    while que:
        now,cost = que.pop()
        path[now]=""
        dp[now]=cost
        for n,c in AB[now]:
            if n not in path:
                que.append((n,cost+c))
    for i in range(Q):
        x,y=map(int,input().split())
        print(dp[x]+dp[y])
main()
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
xor = []
for i in range(len(a)):
	for k in range(i,len(a)):
		xor.append(int(bin(a[i]^a[k]),0))
for i in a:
	if i not in xor:
		print("No")
		exit()
print("Yes")

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
sum = 0
for i in a:
	sum^=i
if sum == 0:
	print("Yes")
else:
	print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = [pow(2, i, mod) for i in range(60)]
l0 = [n] * 60
l1 = [0] * 60
for i in a:
    t = list(format(i, "b"))
    for j in range(len(t)):
        if int(t[j]) == 1:
            l0[len(t) - 1 - j] -= 1
            l1[len(t) - 1 - j] += 1
ans = 0
for i in range(60):
    ans += (l0[i] * l1[i] * p[i]) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = [pow(2, i, mod) for i in range(60)]
ans = 0
for i in range(60):
    c = 0
    for j in a:
        if (j >> i) & 1:
            c += 1
    ans += (c * (n - c) * p[i]) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))

A.sort()
A = deque(A)
while len(A) > 1:
  s = []
  for i in range(len(A)-1):
    div = A[-1] % A[0]
    A.pop()
    if (div != 0) and (div not in s):
      s.append(div)
  s.append(A[0])
  s.sort()
  A = deque(s)
print(*A)

### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))

A.sort()
A = deque(A)
while len(A) > 1:
  s = []
  for i in range(len(A)-1):
    div = A[-1] % A[0]
    A.pop()
    if div != 0:
      s.append(div)
  s.append(A[0])
  s.sort()
  A = deque(s)
print(*A)
### BUGGY CODE ###

import bisect

n = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]
        l = bisect.bisect(L[j+1:n], a+b-1)
        ans += l
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
L = sorted(map(int, input().split()))
ans = 0
for i in range(n):
    a = L[i]
    for j in range(i+1, n):
        b = L[j]
        k = bisect.bisect_left(L, a+b)
        if k > j:
            ans += k - j - 1
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
for _ in range(q):
    t=list(map(str,input().split()))
    if int(t[0])==1:
        s=s[::-1]
        #print(s)
    if int(t[0])==2:
        f=int(t[1])
        if f==1:
            p=t[2]
            s=p+s
            #print(s)
        if f==2:
            z=t[2]
            s=s+z
            #print(s)
print(s)

### FIXED CODE ###

s=input()
q=int(input())
cn=0
l1=""
l2=""
for i in range(q):
    p=input()
    if p=="1":
        cn+=1
    else:
        _,f,c=p.split()
        if f=="1":
            if cn%2==0:
                l1+=c
            else:
                l2+=c
        else:
            if cn%2==1:
                l1+=c
            else:
                l2+=c
if cn%2==1:
    s=s[::-1]
    l1,l2=l2,l1
print(l1[::-1]+s+l2)
### BUGGY CODE ###

N = int(input())

keihin = []

for i in range(N):
    s = input()
    if s in keihin:
        pass
    else:
        keihin.append(s)
    
print(len(keihin))

### FIXED CODE ###

N = int(input())

keihin = []

for i in range(N):
    keihin.append(input())
    
print(len(set(keihin)))
### BUGGY CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]
    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
                self.allunite(self.root(x),self.root(y))
            else:
                self.roots[self.root(y)]=self.root(x)
                self.allunite(self.root(y),self.root(x))
    def find(self,x):
        unit=[]
        for i in range(self.n):
            if x==self.roots[i]:
                unit.append(i)
        return unit
    def allunite(self,x,y):
        unit=self.find(x)
        for i in range(len(unit)):
            self.roots[unit[i]]=y
            return
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)


road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

### FIXED CODE ###

from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]


    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)



count=defaultdict(lambda:0)
point=[]
for i in range(N):
    a=road.root(i)
    b=train.root(i)
    l=[a,b]
    point.append(l)
    count[str(l)]+=1
for i in point:
    print(count[str(i)],end=" ")
### BUGGY CODE ###

N = int(input())
S = str(input())


ans = 4000000
for l in range(N):#Leader
    changecount = 0
    for i in range(N):
        if(i<l and S[i] == "W") or (i>l and S[i] == "E"):
            changecount+=1
    ans = min(ans,changecount)
print(ans)


### FIXED CODE ###

import sys
# N,M = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())
# a,b,c = [int(n) for n in input().split()]
# ←W, E→
# EEELWWWWにしたい
N = int(input())
S = str(input())
cusum = [0]*N
cusum[0] = 1 if S[0] == 'E' else 0

for i in range(1,N):
    cusum[i] = cusum[i-1]
    if S[i] == 'E':
        cusum[i]+=1
ans = 999999999999
for i in range(N):
    if i == 0:
        tmp = cusum[N-1] - cusum[0]
    elif i == N-1:
        tmp = N-1 - cusum[N-2]
    else:
        tmp = i - cusum[i-1]
        tmp += cusum[N-1] - cusum[i]
    ans = min(tmp, ans)
print(ans)
### BUGGY CODE ###

import collections


N = int(input()) #1行目のNを取得する
s = [input() for i in range(N)] #複数行の数値の入力を取得

counted = collections.Counter(s)
#最頻値が同値である場合全て出力したい
#頻出数ではなく、文字だけ出力したい
ret = [letter for letter,count in counted.most_common() if count == counted.most_common()[0][1]]
new_ret=sorted(ret)
for i in range(len(new_ret)):
    print(new_ret[i])# ['a', 'c']

### FIXED CODE ###

from collections import Counter


N = int(input()) #1行目のNを取得する
s = [input() for i in range(N)] #複数行の数値の入力を取得
ans=[]

counted = Counter(s)#
counted_sort=counted.most_common()

for i in range(len(counted_sort)):
    if counted_sort[i][1]==counted_sort[0][1]:
        ans.append(counted_sort[i][0])


[print(i) for i in sorted(ans)]
### BUGGY CODE ###

import itertools
import sys


def query(li):
    for i in range(n):
        li[i] += 1
    sys.stdout.flush()
    return input()

n = int(input())
a = [0] * (2*n)
tmp = [j for j in range(n)]
ans = query(tmp)
if ans == "Blue":
    b = 0
    r = n
else:
    b = n
    r = 0
while abs(b - r) > 1:
    mid = (b+r) // 2
    tmp = [j + mid for j in range(n)]
    if query(tmp) == "Blue":
        b = mid
    else:
        r = mid
ans = [None]*(2*n)
if b < r:
    ans[b] = "B"
    ans[b+n] = "R"
else :    
    ans[r] = "R"
    ans[r+n] = "B"

min_rb = min(r, b)
tmp = [j + min_rb + 1 for j in range(n-1)]
tmp2 = [(j + min_rb + n + 1) % (2*n) for j in range(n-1)]

for i in range(2*n):
    if ans[i] is None:
        if i in tmp:
            c = query(tmp2+[i])
        else:
            c = query(tmp+[i])
    if c == "Blue":
        ans[i] = "B"
    else:
        ans[i] = "R"
print("! ", "".join(ans))

### FIXED CODE ###

import sys


def query(li):
    # tmp_b = 0
    # tmp_r = 0
    # for i in li:
    #     if s[i] == "B":
    #         tmp_b += 1
    #     else:
    #         tmp_r += 1

    for i in range(len(li)):
        li[i] += 1
    print("?", *li)

    # if tmp_b > tmp_r:
    #     return "Blue"
    # else:
    #     return "Red"

    sys.stdout.flush()
    res = input()
    return res

n = int(input())
# s = input()

tmp = [j for j in range(n)]
ans = query(tmp)
if ans == "Blue":
    b = 0
    r = n
else:
    b = n
    r = 0

while abs(b - r) > 1:
    mid = (b + r) // 2
    tmp = [j + mid for j in range(n)]
    if query(tmp) == "Blue":
        b = mid
    else:
        r = mid
ans = [None]*(2*n)

if b < r:
    ans[b] = "B"
    ans[(b+n) % (2*n)] = "R"
else:
    ans[r] = "R"
    ans[(r+n) % (2*n)] = "B"

min_rb = min(r, b)
tmp = [j + min_rb + 1 for j in range(n-1)]
tmp2 = [(j + min_rb + n + 1) % (2*n) for j in range(n-1)]

for i in range(2*n):
    if ans[i] is None:
        if i in tmp:
            c = query(tmp2+[i])
        else:
            c = query(tmp+[i])
    else:
        continue
    if c == "Blue":
        ans[i] = "B"
    else:
        ans[i] = "R"
print("!", "".join(ans))
### BUGGY CODE ###

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2


countlist=dict()
check=set()


for i in range(1,N+1):
    countlist[S[i]]=countlist.get(S[i],0)+1
    check=check|{S[i]}
    
    





ANS=int(countlist.get(0,0))



for i in check:
    ANS+=tr(int(countlist[i]))



print(ANS)



### FIXED CODE ###

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2


countlist=dict()
check=set()


for i in range(1,N+1):
    countlist[S[i]]=countlist.get(S[i],0)+1

    
    


ANS=countlist.get(0,0)

for i in countlist.keys():
    ANS+=tr(countlist[i])



print(ANS)
### BUGGY CODE ###

import itertools
N = int(input())
a = list(map(int, input().split()))

ans = 'No'

for i in itertools.permutations(a):
    count = 0
    for j in range(1, len(i)):
        if (i[j-1] * i[j]) % 4 == 0:
            count += 1
        else:
            pass
    if count == N-1:
        ans = 'Yes'
        break

print(ans)

### FIXED CODE ###

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

cnt2 = 0  # 2で割り切れる回数
cnt4 = 0  # 4で割り切れる回数

for i in range(N):
    if a[i] % 4 == 0:
        cnt4 += 1
    elif a[i] % 2 == 0:
        cnt2 += 1

if N-max(cnt2-1, 0) <= cnt4*2+1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
N = int(input())
a = list(map(int,input().split(" ")))

memo = [ [-1]*N  for _ in range(N) ]


def dfs(l,r,turn):
    if l == r:
        return 0

    if memo[l][r-1] != -1:
        return memo[l][r-1]

    if turn % 2 == 0:
        ret = max(a[l] + dfs(l+1,r,(turn+1)%2),a[r-1] + dfs(l,r-1,(turn+1)%2))
    else:
        ret = min(-a[l] + dfs(l+1,r,(turn+1)%2),-a[r-1] + dfs(l,r-1,(turn+1)%2))

    memo[l][r-1] = ret
    return memo[l][r-1]

ans = dfs(0,N,0)
print(ans)




### FIXED CODE ###

import sys
N = int(input())
a = list(map(int,input().split(" ")))

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

for l in range(N-1,-1,-1):
    for r in range(l,N):
        turn = ((N - r) + l + 1) % 2

        if turn == 0:
            if r > 0 and l < N-1:
                dp[l][r] = max(a[l] + dp[l+1][r],a[r]+dp[l][r-1])
            elif l < N-1:
                dp[l][r] =  a[l] + dp[l+1][r]
            else:
                dp[l][r] =  a[r] + dp[l][r-1]
        else:
            if r > 0 and l < N-1:
                dp[l][r] = min(-a[l] + dp[l+1][r],-a[r]+dp[l][r-1])
            elif l < N-1:
                dp[l][r] = -a[l] + dp[l+1][r]
            else:
                dp[l][r] = -a[r] + dp[l][r-1]
print(dp[0][N-1])
### BUGGY CODE ###

import math

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

h.sort(reverse=True)

if n <= k:
    print(0)
else:
    for _ in range(k):
        h.pop(0)
    ans = sum(h)
    print(ans)

### FIXED CODE ###

import math

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

h.sort(reverse=True)

if n <= k:
    print(0)
else:
    x = n - k
    del h[0:k]
    ans = sum(h)
    print(ans)
### BUGGY CODE ###

n = int(input())
strlist = list(input())

for i in reversed(range(1,n)):
    if strlist[i] == strlist[i-1]:
        strlist.pop(i)
print(len(strlist))

### FIXED CODE ###

n = int(input())
strlist = list(input())
count = 0
for i in reversed(range(1,n)):
    if strlist[i] == strlist[i-1]:
        count+=1
        
print(len(strlist)-count)
### BUGGY CODE ###

def main():
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    @lru_cache(maxsize=None)
    def dfs(v, par=-1):
        """最長有向パスに含まれる頂点数"""
        ret = 0
        for u in g[v]:
            if u == par: continue
            ret = max(ret, dfs(u, v))
        return ret + 1

    n, m = map(int, readline().split())

    g = tuple(set() for _ in range(n))
    for _ in range(m):
        x, y = (int(c) - 1 for c in input().split())
        g[x].add(y)

    ret = 0
    for i in range(n):
        ret = max(ret, dfs(i))
    print(ret - 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)


def rec(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for nv in g[v]:
        res = max(res, rec(nv) + 1)
    dp[v] = res
    return res


N, M = map(int, input().split())
g = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    g[x].append(y)

dp = [-1 for _ in range(N)]

ans = 0
for t in range(N):
    ans = max(ans, rec(t))
print(ans)
### BUGGY CODE ###

N = int(input())
a_list = [int(input()) for _ in range(N)]

from bisect import *

que = []

ans = 0
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        ans += 1
    else:
        idx = bisect_right(que, a-1)
        if idx == 0:
            insort_left(que, a)
            ans += 1
        else:
            # b = que[idx-1]
            #if a != b:
            que[idx-1] = a
            #idx2 = bisect_right(que, a-1)

print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_right, insort_left
from collections import deque
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []
que = deque(que)

ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        min_num = a
        ans += 1
    else:
        idx = bisect_right(que, a-1)

        if idx == 0:
            que.appendleft(a)
            ans += 1
            min_num = a
        else:
            idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    #print(que, min_num)
print(ans)
### BUGGY CODE ###

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

# input
n = int(input())
a_list = list(map(int, input().split()))

a_count_list = []

a_dic = {}

for i in range(len(a_list)):
    key = a_list[i]
    if key in a_dic:
        a_dic[key] += 1
    else:
        a_dic[key] = 1

a_solution_dic = {}
a_solution_dic_at_k = {}
for key in a_dic:
    if key in a_solution_dic:
        continue
    else:
        a_solution_dic[key] = int(a_dic[key] * (a_dic[key]-1) / 2)
        a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)


for k, ak in enumerate(a_list):
    sum_select = 0
    for key in a_dic:
        if ak == key:
            sum_select += a_solution_dic_at_k[key]
        else:
            sum_select += a_solution_dic[key]

    print(sum_select)


### FIXED CODE ###

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

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
all_sum_select = 0
for key in list(a_dic.keys()):
    all_sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select_at_k = all_sum_select + int((a_dic[ak]-1) * (a_dic[ak]-2) / 2) \
                       - int(a_dic[ak] * (a_dic[ak]-1) / 2)


    print(sum_select_at_k)
### BUGGY CODE ###

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

Y = X.copy()
Y.sort()

for x in X:
    Y.remove(x)
    print(Y[N//2-1])
    Y.append(x)
    Y.sort()

### FIXED CODE ###

from copy import deepcopy

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

Y = X.copy()
Y.sort()

for x in X:
    if x <= Y[N//2-1]:
        print(Y[N//2])
    else:
        print(Y[N//2-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

    total = sum(A)
    for i in range(N):
        num = i+1
        totali = 0
        for j in range((N-1)//2):
            if num >= N:
                num -= N
            totali += A[num]
            num += 2
        ans= total - 2*totali
        print(ans,end = " ")



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    total = sum(A)
    num = 1
    totali = 0
    for j in range((N-1)//2):
        if num >= N:
            num -= N
        totali += A[num]
        num += 2
    ans= total - 2*totali
    print(ans,end = " ")
    for i in range(1,N,1):
        ans = (A[i-1] - ans//2)*2
        print(ans,end = " ")


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

n = int(input())
ta = [[int(i) for i in input().split()] for j in range(n)]

a = ta[0][0]
b = ta[0][1]
for i in range(1, n):
    tempa = ta[i][0]
    tempb = ta[i][1]
    j = 2
    while(tempa < a or tempb < b):
        tempa = ta[i][0] * j
        tempb = ta[i][1] * j
        j += 1

    a = tempa
    b = tempb

print(a+b)


### FIXED CODE ###

import math

n = int(input())
ta = [[int(i) for i in input().split()] for j in range(n)]

a = 1
b = 1
for i in range(n):
    #n = max(math.floor(a/ta[i][0]), math.floor(b/ta[i][1]))
    n = max(~-a//ta[i][0] + 1, ~-b//ta[i][1] + 1)
    a = n * ta[i][0]
    b = n * ta[i][1]

print(a+b)
### BUGGY CODE ###

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

def D159_1():
    N = int(input())
    A = input().split()
    tmp = 0
    idx = list(set(A))
    value = [ A.count(_) for _ in idx ]
    for n in value:
        tmp += combi(n)
    #sum = 0
    for i in A:
        j = idx.index(i)
        #sum += tmp - combi(j) + combi(j-1)
        print(int(tmp - combi(value[j]) + combi(value[j]-1)))


if __name__ == "__main__":
    D159_1()

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
import collections
A_count = collections.Counter(A)
 
import math
sum_ = 0
for ai in A_count:
    sum_ += (A_count[ai] * (A_count[ai] - 1)) // 2
 
for ai in A:
    #print(sum_ - (A_count[ai] * (A_count[ai] - 1)) // 2 + (A_count[ai] - 1) * (A_count[ai] - 2)) // 2
    l = A_count[ai] * (A_count[ai] - 1) // 2
    m = (A_count[ai] - 1) * (A_count[ai] - 2) // 2
    print(sum_ - l + m)