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

n,w = map(int,input().split())
dp = [[0 for i in range(w+1)]for j in range(n+1)]

for i in range(n):
    weight,value = map(int,input().split())
    for j in range(w+1):
        if j >= weight:
            dp[i+1][j] = max(dp[i][j-weight]+value,dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])

### FIXED CODE ###

n,w = map(int,input().split())
weight = [0]*n
value = [0]*n
for i in range(n):
    weight[i],value[i] = map(int,input().split())
dp = [[1000000001 for i in range(max(value)*n+1)]for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(len(dp[0])):
        if j >= value[i]:
            dp[i+1][j] = min(dp[i][j-value[i]]+weight[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for i,j in enumerate(dp[n]):
    if j <= w:
        ans = max(ans,i)

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

a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0
 
#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v
 
  wv_list.append([w, v])
 
#初期化
#とりあえず、全部最大になるように
n_list = [[float('inf') for i in range(max_value + 1)] for j in range(N)]
 
#
n_list[0][wv_list[0][1]] = wv_list[0][0]
 
for i in range(1, N):
 
  for j in range(max_value):
 
    s = j + wv_list[i][1]
 
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
    n_list[i][wv_list[i][1]] = wv_list[i][0]
 
for i in range(1, max_value):
 
  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break


### FIXED CODE ###

a= input().split()
N = int(a[0])
W = int(a[1])
wv_list = []
max_value = 0

#価値と重さのやつをリストにしてる
for i in range(N):
  b = input().split()
  w = int(b[0])
  v = int(b[1])
  max_value += v

  wv_list.append([w, v])

#初期化
#とりあえず、全部最大になるように
inf=float('inf')
n_list = [[inf for i in range(max_value + 1)] for j in range(N)]

#最初のアイテムに関して、重みを適切な価値のところにいれている
n_list[0][wv_list[0][1]] = wv_list[0][0]

for i in range(1, N):
  # 今まで全く選んでなかった場合に、i番目のアイテムを選んだ時
  n_list[i][wv_list[i][1]] = wv_list[i][0]
  for j in range(max_value):

    s = j + wv_list[i][1]
    #アイテムを選んだらこうなりますよってのを更新
    if s <= max_value:
      n_list[i][s] = min(n_list[i - 1][j] + wv_list[i][0], n_list[i][s])

    #選ばんかったらこうなりますよってのを更新？
    n_list[i][j] = min(n_list[i - 1][j], n_list[i][j])
  
for i in range(1, max_value):

  if n_list[-1][-i] <= W:
    print(max_value - i + 1)
    break
### BUGGY CODE ###

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

use = []
for i in set(a):
    can = a.count(i) // 2
    if can > 0:
        for j in range(can):
            use.append(i)
use.sort()
if len(use) > 1:
    print(use[-1] * use[-2])
else:
    print(0)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tobasu = 0
one = 0
two = 0
for i in range(len(a) - 1):
    if tobasu == 1:
        tobasu = 0
        continue
    if a[i] == a[i + 1] and one == 0:
        tobasu = 1
        one = a[i]
    elif a[i] == a[i + 1] and one != 0 and two == 0:
        two = a[i]
        break
print(one * two)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v):
	if v == bef_v :
		seen[v] = 0;
	else :
		#print(bef_v,v,G[v],weight[bef_v][v],seen[bef_v])
		ind = 0;
		for i in range(len(G[bef_v][0])) :
			if G[bef_v][0][i] == v :
				ind = i;
		if G[bef_v][1][ind] % 2 :
			seen[v] = int(not seen[bef_v]);
		else :
			seen[v] = seen[bef_v];
	
	for next_v in G[v][0] :
		if seen[next_v]==-1 :
			dfs(G,next_v,v);


n = int(input());
G = [[0]*2 for i in range(n) ];
for i in range(n) :
	G[i][0] = [];
	G[i][1] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u][0].append(v);
	G[v][0].append(u);
	G[u][1].append(w);
	G[v][1].append(w);


seen = [-1]*n;
dfs(G,0,0);

for i in range(n):
	print(seen[i]);
	


### FIXED CODE ###

import sys

sys.setrecursionlimit(500*500);

def dfs(G,v,bef_v,ind_num):
	if v == bef_v :
		seen[v] = 0;
	else :
		#print(bef_v,v,G[v],weight[bef_v][v],seen[bef_v])
		if G[bef_v][1][ind_num] % 2 :
			seen[v] = int(not seen[bef_v]);
		else :
			seen[v] = seen[bef_v];
	
	for i in range(len(G[v][0])) :
		next_v = G[v][0][i];
		if seen[next_v]==-1 :
			dfs(G,next_v,v,i);


n = int(input());
G = [[0]*2 for i in range(n) ];
for i in range(n) :
	G[i][0] = [];
	G[i][1] = [];
for i in range(n-1) :
	s = input().split(' ');
	u = int(s[0])-1;
	v = int(s[1])-1;
	w = int(s[2]);
	G[u][0].append(v);
	G[v][0].append(u);
	G[u][1].append(w);
	G[v][1].append(w);


seen = [-1]*n;
dfs(G,0,0,0);

for i in range(n):
	print(seen[i]);
### BUGGY CODE ###

from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(list)
block = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].append(b)
    friends[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)
#print(friends)
#print(block)

roopname = []
roop = defaultdict(list)
seen = [0]*n


for i in range(n):
    if not seen[i]==0:
        continue
    seen[i] = i+1
    roopname.append(i+1)
    roop[i+1].append(i+1)
    queue = deque(friends[i+1])
    while queue:
        p = queue.popleft()
        if  not seen[p-1]==0:continue
        seen[p-1] = i+1
        roop[i+1].append(p)
        for j in friends[p]:
            if seen[j-1]==0:
                queue.append(j)
#print(roopname)
#print(roop)
#print(seen)
ans = []
for i in range(n):
    fsum = 0
    for j in friends[i+1]:
        if j in roop[seen[i]]:
            fsum += 1
            
    bsum = 0
    for j in block[i+1]:
        if j in roop[seen[i]]:
            bsum += 1
    
    ans.append(len(roop[seen[i]])-bsum-fsum-1)

L=[str(a) for a in ans]
L=" ".join(L)
print(L)

### FIXED CODE ###

from collections import defaultdict, deque
n, m, k = map(int, input().split())
friends = defaultdict(set)
block = defaultdict(set)
for _ in range(m):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    block[c].add(d)
    block[d].add(c)
#print(friends)
#print(block)

roopname = []
roop = defaultdict(set)
seen = [0]*n


for i in range(n):
    if not seen[i]==0:
        continue
    seen[i] = i+1
    roopname.append(i+1)
    roop[i+1].add(i+1)
    queue = deque(friends[i+1])
    while queue:
        p = queue.popleft()
        if  not seen[p-1]==0:continue
        seen[p-1] = i+1
        roop[i+1].add(p)
        for j in friends[p]:
            if seen[j-1]==0:
                queue.append(j)
#print(roopname)
#print(roop)
#print(seen)
ans = [len(roop[seen[i]])-len(roop[seen[i]]&friends[i+1])-len(roop[seen[i]]&block[i+1])-1 for i in range(n)]

    

L=[str(a) for a in ans]
L=" ".join(L)
print(L)
### BUGGY CODE ###

# @uthor : Kaleab Asfaw
import sys

input = sys.stdin.readline

def product(lst):
    x = 1
    for i in lst:
        x *= i
    return x

def main(n, k, lst):
    prev = product(lst[:k])
    for i in range(n-k):
        curr = (prev / lst[i]) * lst[i+k]
        if curr > prev: print("Yes")
        else: print("No")
        prev = curr
    
    


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




### FIXED CODE ###

# @uthor : Kaleab Asfaw
import sys

input = sys.stdin.readline

def main(n, k, lst):
    for i in range(n-k):
        if lst[i+k] > lst[i]:print("Yes")
        else: print("No")
        
    
n, k = list(map(int, input().split()))
lst = list(map(int, input().split()))
main(n, k, lst)
### BUGGY CODE ###

import numpy as np


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
for k in range(K):
    B = np.zeros(N + 1, dtype=int)
    for i in range(N):
        a = A[i]
        B[max(0, i - a)] += 1
        B[min(N, i + a + 1)] -= 1
    A = np.cumsum(B)[:-1]
    if np.all(A == N):
        break
print(' '.join(map(str, A)))

### FIXED CODE ###

import numpy as np
from numba import njit


@njit
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            a = A[i]
            B[max(0, i - a)] += 1
            B[min(N, i + a + 1)] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == N):
            return A
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))
### BUGGY CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

for i in range(n):
    list=a[:]
    list.pop(i)
    print(max(list))

### FIXED CODE ###

n = int(input())
a = list(map(int, [input() for i in range(n)]))

list=a[:]
list.sort(reverse=True)
max1 = list[0]
max2 = list[1]

for i in range(n):
    if a[i]==max1:
        print(max2)
    else:
        print(max1)
### BUGGY CODE ###

from scipy.misc import comb
N,a,b=map(int,input().split())
MOD=10**9+7
cnt=0
for i in range(1,N+1):
  cnt+=comb(N, i, exact=True)
A=comb(N, a, exact=True)
B=comb(N, b, exact=True)
cnt=cnt-A-B
ans=cnt%MOD
print(ans)

### FIXED CODE ###

N,a,b=map(int,input().split())
MOD=10**9+7
def comb(n,k):
  tmp=1
  for i in range(n-k+1,n+1):
    tmp*=i
    tmp%=MOD
  for i in range(1,k+1):
    tmp*=pow(i,MOD-2,MOD)
    tmp%=MOD
  return tmp
ans = pow(2,N,MOD) - 1 - comb(N,a) - comb(N,b)
print(ans%MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(k + 1)]

for i in range(n + 1):
    dp[0][i] = 1
for i in range(a[0] + 1):
    dp[i][1] = 1

for i in range(1, k + 1):
    for j in range(2, n + 1):
        for w in range(min(a[j - 1], i) + 1):
            dp[i][j] += dp[i - w][j - 1]
        dp[i][j] %= (10 ** 9 + 7)
print(dp[k][n])

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(n + 1):
    dp[i][0] = 1
for i in range(a[0] + 1):
    dp[1][i] = 1

for i in range(2, n + 1):
    for j in range(1, k + 1):
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
        if j > a[i - 1]:
            dp[i][j] -= (dp[i - 1][j - a[i - 1] - 1]) % mod
        dp[i][j] %= mod
print(dp[n][k])
### BUGGY CODE ###

from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    newa = [0 for _ in range(n)]
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        newa[l] += 1
        if r + 1 < n:
            newa[r + 1] -= 1
    a = list(accumulate(newa))
    if all(i == n for i in a):
        break
print(*a)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    newa = [0 for _ in range(n)]
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        newa[l] += 1
        if r + 1 < n:
            newa[r + 1] -= 1
    a = list(accumulate(newa))
    if all(i == n for i in a):
        break
print(*a)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
A=a[0]
for i in range(n-1):
    if i==0:
        ans=abs(sum(a)-2*A)
    else:
        ans=min(abs(sum(a)-2*A),ans)
    A+=a[i+1]
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sum(a)
A=a[0]
for i in range(n-1):
    if i==0:
        ans=abs(b-2*A)
    else:
        ans=min(abs(b-2*A),ans)
    A+=a[i+1]
print(ans)
### BUGGY CODE ###

from collections import deque

S = deque([x for x in input()])
Q = int(input())
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        T = int(inp)
        S = deque(list(S)[::-1])
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            S.appendleft(C)
        else:
            S.append(C)

print("".join(S))

### FIXED CODE ###

from collections import deque

S = deque([x for x in input()])
Q = int(input())
switch = 0
for _ in range(Q):
    inp = input()
    if len(inp) == 1:
        T = int(inp)
        if switch:
            switch = 0
        else:
            switch = 1
    else:
        T, F = map(int, inp.split()[:2])
        C = inp.split()[-1]
        if F == 1:
            if switch:
                S.append(C)
            else:
                S.appendleft(C)
        else:
            if switch:
                S.appendleft(C)
            else:
                S.append(C)
if switch:
    print("".join(list(S)[::-1]))
else:
    print("".join(S))
### BUGGY CODE ###

n = int(input())
candidate = {}
for i in range(n):
  inp = input()
  if inp not in candidate:
    candidate[inp] = 1
  else:
    candidate[inp] += 1
ans = [j[0] for j in candidate.items() if j[1] == max(candidate.values())]
ans.sort()
print('\n'.join(ans))

### FIXED CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline())
S = sys.stdin.read().split()

count = Counter(S)
max_num = max(count.values())
max_list = [i for i,j in count.items() if j==max_num]

max_list.sort()
print('\n'.join(max_list))
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
    S.append(tuple(map(int, input().split())))

dp = [0] * (N + 1)
dp[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        dp[i] += sum(dp[LL:RR+1])
    dp[i] %= MOD

print(dp[N])


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
S = []
for _ in range(K):
    S.append(tuple(map(int, input().split())))

dp = [0] * (N + 1)
dp[1] = 1
sum_list = [0] * (N + 1)
sum_list[1] = 1

for i in range(2, N+1):
    for L, R in S:
        RR = i - L
        if RR <= 0:
            continue
        LL = max(1, i-R)
        if LL <= RR:
            t = sum_list[RR] - sum_list[LL-1]
            dp[i] += t
    sum_list[i] = (sum_list[i-1] + dp[i]) % MOD
    dp[i] %= MOD

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

input = raw_input

N,Q = map(int,input().split(" "))
s=list(input())
ju = []
for i in range(Q):
    ju.append(input().split(" "))

mem = [0] * N
def isdead(xp):
    if mem[xp] == 1:
        return True
    elif mem[xp] == 2:
        return False
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0 or xp > N-1:
            mem[oxp] = 1
            return True
    mem[oxp] = 2
    return False

def mid(x1,x2):
    return int((x1+x2)/2)

p1 = 0
p3 = N-1
p2 = mid(p1,p3)
ap = -1

for i in range(2,N):
    for j in range(0,N,int(N/i)):
        if not isdead(j):
            ap = j
            break
    if ap != -1:
        break
if ap == -1:
    print(0)
    exit()

#left
p1 = 0
p3 = ap
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdead(p2):
        p1,p2 = p2,mid(p2,p3)
    else:
        p2,p3 = mid(p1,p2),p2
if isdead(p1):
    p = p3
else:
    p = p1
#right
p1 = ap
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdead(p2):
        p2,p3 = mid(p1,p2),p2
    else:
        p1,p2 = p2,mid(p2,p3)
if isdead(p3):
    q = p1
else:
    q = p3


if p > q:
    print(0)
else:
    print(q-p+1)


### FIXED CODE ###

input = raw_input

N,Q = map(int,input().split(" "))
s=list(input())
ju = []
for i in range(Q):
    ju.append(input().split(" "))

def isdeadleft(xp):
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0:
            return True
        if xp > N-1:
            xp = N-1
    return False

def isdeadright(xp):
    oxp = xp
    for i in range(Q):
        com = ju[i]
        if s[xp] == com[0]:
            if com[1] == "L":
                xp -= 1
            else:
                xp += 1
        if xp < 0:
            xp = 0
        if xp > N-1:
            return True
    return False

def mid(x1,x2):
    return int((x1+x2)/2)

if isdeadleft(N-1) or isdeadright(0):
    print(0)
    exit()

#left
p1 = 0
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdeadleft(p2):
        p1,p2 = p2,mid(p2,p3)
    else:
        p2,p3 = mid(p1,p2),p2
if isdeadleft(p1):
    p = p3
else:
    p = p1
#right
p1 = 0
p3 = N-1
p2 = mid(p1,p3)
while p3 - p1 != 1:
    if isdeadright(p2):
        p2,p3 = mid(p1,p2),p2
    else:
        p1,p2 = p2,mid(p2,p3)
if isdeadright(p3):
    q = p1
else:
    q = p3

if p > q:
    print(0)
else:
    print(q-p+1)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return int(x*y)//int(gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A)
ans = 0
for i in range(N):
    B[i] = int(global_lcm//A[i])
    ans += B[i] % MOD
    ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce, lru_cache

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return int(x*y)//int(gcd(x, y))

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A) % MOD
ans = 0
for i in range(N):
    ans += (global_lcm*pow(A[i], MOD-2, MOD)) % MOD
    ans %= MOD

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

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [0 for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                newq.add((h, w))
                for dh, dw in dhdw:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '#':
                            continue
                        q_.add((h+dh, w+dw))
                        M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                lh = - min(2, h)
                hh = min(3, H - h) 
                for dh in range(lh, hh):
                    lw = - min(2, w)
                    hw = min(3, W - w)
                    for dw in range(lw, hw):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

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

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

m = 10**10
for i in range(n):
    x = sum(a[:i])
    y = sum(a[i:])
    m = min(abs(x-y),m)
print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 10**10
x = sum(a)
y = 0
for i in range(n):
    x -= a[i]
    y += a[i]
    m = min(abs(x-y),m)
print(m)
### BUGGY CODE ###

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

ans = 0
for i in range(1, N+1):
    num = A.count(i)
    ans += num * (num - 1) // 2
for k in range(1, N+1):
    n = A.count(A[k-1])
    ans_ = ans - (n - 1)
    print(ans_)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = tuple(map(int, input().split()))
A_count = Counter(A)
ans = 0
for i, j in A_count.items():
    ans += j * (j - 1) // 2
for k in range(1, N+1):
    n = A_count[A[k-1]]
    ans_ = ans - (n - 1)
    print(ans_)
### BUGGY CODE ###

from math import gcd, sqrt, ceil
_, *aa = map(int, open(0).read().split())

from collections import defaultdict
def factorize(n):
    factors = set()
    if n % 2 == 0:
        factors.add(2)
    while n % 2 == 0:
        n //= 2
    for i in range(3, ceil(sqrt(n + 1)) + 1):
        if n % i == 0:
            factors.add(i)
        while n % i == 0:
            n //= i
    if n > 2:
        factors.add(n)
    return factors

def main(aa):
    pair_co = True
    min_factors = None
    max_factors = set()
    for a in aa:
        factors = factorize(a)
        new_max_factors = max_factors | factors
        if len(new_max_factors) < len(max_factors) + len(factors):
            pair_co = False
        max_factors = new_max_factors
        if min_factors is not None:
            min_factors &= factors
        else:
            min_factors = factors
#     if min_factors:
#         return 'not coprime'
#     elif pair_co
    if pair_co:
        return 'pairwise coprime'
    elif min_factors:
        return 'not coprime'
    else:
        return 'setwise coprime'
        

print(main(aa))

### FIXED CODE ###

from math import gcd, sqrt, ceil
from functools import reduce

def sieve(n):
    A = list(range(n+1))
    for i in range(2, n+1 ,2):
        A[i] = 2
    for j in range(3, ceil(sqrt(n+1))+1, 2)[::-1]:
        for i in range(j, n+1, j):
            A[i] = j
    return A

def factorize(n, A):
    factors = set()
    while n != 1:
        f = A[n]
        factors.add(f)
        n //= f
    return factors

_, *aa = map(int, open(0).read().split())

def main(aa):
    pair_co = True
    A = sieve(10**6)
    all_factors = [0] * (10**6+1)
    for a in aa:
        factors = factorize(a, A)
        for factor in factors:
            if all_factors[factor]:
                pair_co = False
                break
            else:
                all_factors[factor] = 1
        if not pair_co:
            break
    if pair_co:
        return 'pairwise coprime'
    elif reduce(gcd, aa) == 1:
        return 'setwise coprime'
    else:
        return 'not coprime'

print(main(aa))
### BUGGY CODE ###

import numpy as np
import sys

N = int(input())
H = np.array(list(map(int, input().split())))
if all(np.diff(H) >= 0):
  print("Yes")
  sys.exit()
  
for i in range(N):
  h = H.copy()
  h[i] = h[i] - 1
  if all(np.diff(h) >= 0):
    print("Yes")
    sys.exit()
 
print("No")

### FIXED CODE ###

import numpy as np
N = int(input())
H = list(map(int, input().split()))

max = 0
for i in range(N):
  if max < H[i]:
    max = H[i]
  if max - H[i] >= 2:
    print("No")
    exit(0)
print("Yes")