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



import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((N+1,W+1), dtype=np.int64)
    #dp = [[0]*(W+1) for i in range(N+1)]

    #print(dp)
    #print(dp2)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

### FIXED CODE ###

"""memo
    numpyでやるときは配列を一気に更新するが(numpy使いたくないのでやらない)，
    このやり方は後ろの方から更新することで後の更新に影響を与えない(考え方すごい)．
    (参考#9889377)
"""

import sys
input = sys.stdin.readline

def main():
    #1:初期化
    N,W = map(int,input().split())
    dp = [0]*(W+1)

    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(N):
        w, v = map(int,input().split())
        for i in range(W, w-1, -1):
            tmp = dp[i-w] + v
            if dp[i] < tmp:
                dp[i] = tmp
        #print(dp,sep="\n")

    #4:出力
    print(max(dp))

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

def cal(n):
	ans = 1
	for i in range(1,n+1):
		ans *= i
	rm = ans%(10**9 + 7)
	return rm

N = int(input().strip())
print(cal(N))


### FIXED CODE ###

def cal(n):
	ans = 1
	for i in range(n):
		ans = ((i+1) * ans) % (1000000007)
	return ans

N = int(input())
print(cal(N))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[-1]
k=[1,1]
ansk=1
d=[]
renzoku=1
for i in range(m):
 a.append(int(input()))
 if a[i+1]==a[i]+1:
    renzoku=0
a.append(n+1)
for i in range(max(a)):
 s=k[i+1]+k[i]
 k.append(s)
for i in range(m+1):
 d.append(a[i+1]-a[i]-1)
 ansk*=k[d[i]-1]
if renzoku==1:
 print(ansk%1000000007)
else:
 print(0)

### FIXED CODE ###

def Fib(n):
    a=[0,1,1]
    if n<=2:
    	return a[n]
    else:
    	for i in range(n-2):
    		a.append(a[i+1]+a[i+2])
    	return a[n]
n,m=map(int,input().split())
if m==0:
	print(Fib(n+1)%(10**9+7))
	exit()
a=[]
for i in range(m):
	a.append(int(input()))
if a[0]!=1:
	a.insert(0,-1)
if a[-1]!=n-1:
	a.append(n+1)
b=[]
for i in range(len(a)-1):
	b.append(a[i+1]-a[i]-1)
	if a[i+1]-a[i]==1:
		print(0)
		exit()
ans=1
for i in range(len(b)):
	ans*=Fib(b[i])
	ans%=10**9+7
print(ans)
### BUGGY CODE ###

n = int(input())
a_lis = list(map(int, input().split()))
n_a = []
for a in a_lis:
    if a in n_a:
        print('NO')
        exit()
    n_a.append(a)
print('YES')

### FIXED CODE ###

import collections
n = int(input())
a_lis = list(map(int, input().split()))
a_cnt = collections.Counter(a_lis)
for v in a_cnt.values():
    if v >= 2:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

def calc(i,n):
    a = A[i]
    if a==0:
        return 0 if n<0 else N-i-1
    if a>0:
        ok = i
        ng = N
        while ng-ok > 1:
            m = (ok+ng)//2
            if m==i or a*A[m]<=n:
                ok = m
            else:
                ng = m
        return ok-i
    else:
        ok = N
        ng = i
        while ok-ng > 1:
            m = (ok+ng)//2
            if m==i or a*A[m]>n:
                ng = m
            else:
                ok = m
        return N-ok

def is_ok(m):
    k = 0
    for i in range(N-1):
        k += calc(i,m)
        if k >= K: return True
    return False

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
pos = N - bisect(A,0)
zero = A.count(0)
neg = N - pos - zero

def is_ok(m):
    if m < 0:
        k = 0
        l = 1
        for i in range(neg):
            a = A[i]
            while a*A[l] > m:
                l += 1
                if l==N: break
            k += N-l
            if k >= K: return True
            if l==N: break
        return False
    else:
        k = diag = 0
        r = neg-1
        for i in range(neg):
            a = A[i]
            while a*A[r] <= m:
                r -= 1
                if r==-1: break
            k += r+1
            if r>=i: diag += 1
            if r==-1: break
        nz = neg+zero
        l = nz
        for i in range(N-1,nz-1,-1):
            a = A[i]
            while a*A[l] <= m:
                l += 1
                if l==N: break
            k += N-l
            if l<=i: diag += 1
            if l==N: break
        tmp = N*(N-1)//2 - (k-diag)//2
        return tmp >= K

ng = -10**18-1
ok = 10**18+1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(n)]

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

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

xy.sort()
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    x1,x2=xy[i][0],xy[i+1][0]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append([x2-x1,n2])
    edge[n2].append([x2-x1,n1])

xy.sort(key=lambda x: x[1])
for i in range(n-1):
    x1,x2=xy[i][1],xy[i+1][1]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append([x2-x1,n2])
    edge[n2].append([x2-x1,n1])
print(prim_heap())

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
xy=[0]*n
for i in range(n):
    x,y=map(int,input().split())
    xy[i]=[x,y,i]

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

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

xy.sort()
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    x1,x2=xy[i][0],xy[i+1][0]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

xy.sort(key=lambda x: x[1])
for i in range(n-1):
    x1,x2=xy[i][1],xy[i+1][1]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

print(prim_heap())
### BUGGY CODE ###

h, w = map(int, input().split())

lists = []
iti_h = []
iti_w = []
cnt = 0

for i in range(h):
    s = list(input())
    lists.append(s)
    

while True:
    check = 0
    for i in range(h):
        for j in range(w):
            if lists[i][j] == "#":
                iti_h.append(i)
                iti_w.append(j)
                check += 1
    if check == h * w:
        break
    cnt += 1
    for i in range(check):
        if iti_h[i] - 1 >= 0:
            lists[iti_h[i] - 1][iti_w[i]] = "#"
        if iti_w[i] - 1 >= 0:
            lists[iti_h[i]][iti_w[i] - 1] = "#"
        if iti_w[i] + 1 <= w - 1:
            lists[iti_h[i]][iti_w[i] + 1] = "#"
        if iti_h[i] + 1 <= h - 1:
            lists[iti_h[i] + 1][iti_w[i]] = "#"
    iti_h.clear()
    iti_w.clear()
    


print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

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

ans=0

for x in range(n):
  maxC=c[x]
  min1=0
  max1=n-1
  while max1-min1>1:
    zantei=(max1+min1)//2
    if b[zantei]>=maxC:
      max1=zantei
    else:
      min1=zantei
  if b[max1]<maxC:
    ch=max1
  elif b[min1]>=maxC:
    continue
  else:
    
    ch=min1
  
  for y in range(ch+1):
    maxB=b[y]
    max2=n-1
    min2=0
    while max2-min2>1:
      zantei1=(max2+min2)//2
      if a[zantei1]>=maxB:
        max2=zantei1
      else:
        min2=zantei1
    if a[max2]<maxB:
      ch1=max2
    else:
      ch1=min2
      
    ans+=ch1+1
    
print(ans)

### FIXED CODE ###

def bs_left(list, target):
    low = 0
    high = len(list)

    while low < high:
        mid = (low + high) // 2
        if target > list[mid]:
            low = mid + 1
        else:
            high = mid
    return low

def bs_right(list, target):
    low = 0
    high = len(list)
    while low < high:
        mid = (low + high) // 2
        if target < list[mid]:
            high = mid
        else:
            low = mid + 1
    return low

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    ans += (bs_left(A, b) * (n - bs_right(C, b)))
print(ans)
### BUGGY CODE ###

from math import log2, ceil
from bisect import bisect_left, bisect_right

N = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = [True for _ in range(N)]

ans = 0
for i in list(range(N))[::-1]:
    if not b[i]: continue
    t = a[i]
    flg = False
    for j in list(range(ceil(log2(t)), int(log2(t * 2)) + 1))[::-1]:
        pair = 2 ** j - t
        left = bisect_left(a, pair)
        right = bisect_right(a, pair)
        # print(t, pair, a, b, left, right)
        if left == right:
            if left < N and left != i:
                if a[left] == pair and b[left]:
                    b[left] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
        else:
            k = right - 1
            k = min(right - 1, N - 1)
            while k >= max(0, left):
                if a[k] == pair and b[k] and k != i:
                    b[k] = False
                    b[i] = False
                    ans += 1
                    flg = True
                    break
                k -= 1
            if flg:
                break

print(ans)


### FIXED CODE ###

# https://beta.atcoder.jp/contests/agc029/submissions/3804087
from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

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

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

    ans = 1
    th = 1000000000000000000

    for a in A:
        ans *= a
    if ans > th:
        print('-1')
    else:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    ans = 1
    th = 1000000000000000000

    for a in A:
        if a == 0:
            print('0')
            return 0

    for a in A:
        ans *= a
        if ans > th:
            print('-1')
            return 0
    print(ans)


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

def DFS(word,N):
    if len(word)==3:A.add(word)
    if len(word)>3:return
    for i in range(N+1,n):
        DFS(word+s[i],i)


n=int(input())
s=input()
A=set()
for i in range(n):
    DFS(s[i],i)
print(len(A))

### FIXED CODE ###

n=int(input())
a=input()
ans=0
for i in range(1000):
    i=str(i).zfill(3)
    x=a.find(i[0])
    y=a.find(i[1],x+1)
    z=a.find(i[2],y+1)
    if x!=-1 and y!=-1 and z!=-1:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

#%%
def dfs(gr,li,pt,n,fr):
    li[n] += pt
    if(len(gr[n])==1 and gr[n][0]==fr):
        return True
    else:
        for i in gr[n]:
            if(i==fr):continue
            dfs(gr,li,li[n],i,n)
        return True
#%%
def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = [int(x) for x in input().split()]
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = [int(x) for x in input().split()]
        li[p-1] += x

    dfs(gp,li,0,0,-1)
    print(*li)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = input().split()
        li[int(p)-1] += int(x)

    st = []
    seen = set()
    st.append(0)
    while(st):
        x = st.pop()
        if(x in seen):continue
        seen.add(x)
        for i in gp[x]:
            if(i in seen):continue
            li[i]+=li[x]
            st.append(i)
    print(*li)

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

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    ans = 1
    inf = 10**18

    for i in range(len(A)):
        ans *= A[i]

    if ans > inf:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import time
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    ans = 1
    inf = 10**18
    t = time.time()

    if 0 in A:
        print(0)
        exit()

    for i in range(len(A)):
        ans *= A[i]
        if ans > inf :
            print(-1)
            exit()

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

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

ad = dict((i, a.count(i)) for i in set(a))
ans = sum(map(lambda x: x*(x-1)//2,ad.values()))

for i in range(n):
    v = ad[a[i]]
    print(ans-v*(v-1)//2+(v-1)*(v-2)//2)

### FIXED CODE ###

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

ad = {}
for i in range(n) :
    if a[i] in ad :
        ad[a[i]] += 1
    else :
        ad[a[i]] = 1

ans = 0
for v in ad.values():
    ans += v*(v-1)//2

for i in range(n):
    v = ad[a[i]]
    print(ans-v*(v-1)//2+(v-1)*(v-2)//2)
### BUGGY CODE ###

import collections

N = int(input())


s = []
for i in range(N):
    s0 = input()  
    c = collections.Counter(s0)
    s.append(c)

count = 0
for i in range(N):
    for j in range(i+1, N):
        if s[i] == s[j]:
            count += 1

print(count)

### FIXED CODE ###

import collections
import math

N = int(input())

al = "abcdefghijklmnopqrstuvwxyz"
al_dict = {}
for i, c in enumerate(al):
    al_dict[c] = i

ss = []
for i in range(N):
    counts = [0 for i in range(26)]
    for char in input():
        ind = al_dict[char]
        counts[ind] += 1
    counts = [str(count) for count in counts]
    key = ",".join(counts)
    #c = collections.Counter(s0)
    #print(tuple(c))
    ss.append(key)

#print(ss)
cc = collections.Counter(ss)

#print(cc)
out = 0
for count in cc.values():
    if count == 1:
        continue
    out += math.factorial(count) // (math.factorial(count-2) * 2)
print(out)

#for s in ss:
#    for  in s[i+1]:
#        if s[i] == s[j]:
#            count += 1

#print(count)
### BUGGY CODE ###

import heapq as hp
n = int(input())
a = list(map(int, input().split()))
han = list(map(lambda x:x*(-1), a))
hp.heapify(han)
b = hp.heappop(han)*(-1)
che,re = [0 for i in range(b)],[]
for i in a:
    che[i-1] = 1
for i in a:
    if i in re:
        che[i-1] = 0
    else:
        re.append(i)
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
print(che.count(1))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = max(a)
che = [1 for i in range(b)]
for i in a:
    if che[i-1] == 1:
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
        che[i-1] = 2
    elif che[i-1] == 2:
        che[i-1] = 0
ans = 0
for i in a:
    if che[i-1] == 2:
        ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,X):
    if len(X) == 0:
        return N
    if len(X) == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if len(X) == 2:
        return max(X[0][1]*i + X[1][1]*((N-i*X[0][0])//X[1][0]) + (N-i*X[0][0])%X[1][0] for i in range(N//X[0][0]+1))
    if len(X) == 3:
        return max(X[0][1]*i + X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for i in range(N//X[0][0]+1) for j in range((N-i*X[0][0])//X[1][0]+1))
        
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):

        *X, = filter(lambda c: int.__sub__(*c)<0, zip(*C))
        N = small_dp(N, X)
    res = N

    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

from itertools import product

X, Y, Z, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

for aa in sorted((sum(p) for p in product(a, b, c)), reverse=True)[:K]:
    print(aa)


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for k in range(n):
    b = a[:]
    b.pop(k)
    l = len(b)
    for i in range(1,l):
        if b.count(i) >= 2:
            ans[k] += (b.count(i) * (b.count(i) - 1 )) // 2

print(*ans[:], sep='\n')


### FIXED CODE ###

n = int(input())
a = [int(a)-1 for a in input().split()]
cnt = [0]*n
for i in a:
    cnt[i] += 1
total = 0
for i in cnt:
    total += i * (i-1) // 2
for i in a:
    print(total - (cnt[i] - 1))
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[i-t if i>t else 0]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

def GCDonBlack(N,A):
    if sum([a%min(A) for a in A]) == 0:
        return min(A)
    else:
        for i in reversed(range(1,max(A))):
            bar = N-1
            for ele in A:
                if ele % i == 0:
                    bar -= 1
                if bar == 0:
                    return i

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

### FIXED CODE ###

import fractions
def mygcd(N,A,S):
    if S == 'R':
        A.reverse()
    ans = [0, A[0]]
    for i in range(1, N):
        ans.append(fractions.gcd(ans[i],A[i]))
    if S == 'R':
        ans.reverse()
    return ans

def GCDonBlack(N,A):
    L = mygcd(N,A,'L')
    R = mygcd(N,A,'R')
    M = [fractions.gcd(L[i], R[i+1])  for i  in range(0,N)]
    return max(M)

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