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

import sys
from heapq import heapify, heappushpop
from bisect import bisect_left as bisect

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

X, Y, Z, K = MAP()
x = MAP()
y = MAP()
z = MAP()

if X > Z:
	x, z = z, x
	X, Z = Z, X
if Y > Z:
	y, z = z, y
	Y, Z = Z, Y

x.sort()
y.sort()
z.sort()

nums = [0] * K
heapify(nums)

for i in range(X):
	for j in range(Y):
		xy = x[i]+y[j]
		z_idx = bisect(z, nums[0]-xy)
		# print(nums)
		# print(xy, z, z_idx)
		for k in range(z_idx, Z):
			heappushpop(nums, xy+z[k])

nums.sort(reverse=True)
for n in nums:
	print(n)

### FIXED CODE ###

import sys
from heapq import heapify, heappushpop
from bisect import bisect_left as bisect

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

X, Y, Z, K = MAP()
x = MAP()
y = MAP()
z = MAP()

if X > Z:
	x, z = z, x
	X, Z = Z, X
if Y > Z:
	y, z = z, y
	Y, Z = Z, Y

x.sort()
y.sort()
z.sort()

nums = [0] * K
heapify(nums)

for i in range(X-1, -1, -1):
	for j in range(Y-1, -1, -1):
		xy = x[i]+y[j]
		z_idx = bisect(z, nums[0]-xy)
		# print(nums)
		# print(xy, z, z_idx)
		for k in range(z_idx, Z):
			heappushpop(nums, xy+z[k])

nums.sort(reverse=True)
for n in nums:
	print(n)
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]
standard = nums[:]
standard.sort()
ans = 0

for i in range(n):
    p = nums[i]
    x = standard.index(p)
    if abs(x - i) % 2 == 1:
        ans += 1

print(ans // 2)

### FIXED CODE ###

n = int(input())
nums = [[int(input()), i] for i in range(n)]
nums.sort()
ans = 0

for i in range(n):
    if abs (i - nums[i][1]) % 2 == 1:
        ans += 1

print(ans // 2)
### BUGGY CODE ###

x = int(input())
c = 1
for b in range(1, x):
    for p in range(2, x):
        if b**p <= x:
            c = max(c, b**p)
print(c)

### FIXED CODE ###

x = int(input())
c = 1
for b in range(1, x):
    for p in range(2, x):
        if b**p <= x:
            c = max(c, b**p)
        else:
            break
print(c)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
import collections
c = collections.Counter(a)
for i in range(1,max(a)+1):
  if c[i] < i:
    ans += c[i]
  if c[i] > i:
    ans += c[i]-i
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [i for i in a if i <= 10**5]
ans = len(a)-len(b)
import collections
c = collections.Counter(b)
for i in range(0,10**5+1):
  if c[i] < i:
    ans += c[i]
  if c[i] > i:
    ans += c[i]-i
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [[cur_priority, cur]]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, [p, x])
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [(cur_priority, cur)]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, (p, x))
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])
### BUGGY CODE ###

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

dp = [float('inf')] * n
dp[0] = 0

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

print(dp[-1])


### FIXED CODE ###

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

dp = [float('inf')] * n
dp[0] = 0

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

print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        for wa in range(S+1):
            DP[i][wa] = 2*DP[i-1][wa]
            DP[i][wa] %= MOD
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        for wa in range(S+1):
            DP[i][wa] = 2*DP[i-1][wa]
            DP[i][wa] %= MOD
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    print(DP[N][S])
    return


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

s = input()
t = input()

dp = [-1]*(len(t)+1)
dp[0] = 0

for p in range(len(t)):
    sd = s[dp[p] % len(s):]+s[:dp[p] % len(s)]
    d = sd.find(t[p])+1
    if d >= 1:
        dp[p+1] = dp[p]+d
    else:
        print(-1)
        exit()

print(dp[len(t)])


### FIXED CODE ###

import bisect
from collections import defaultdict

S = input()
T = input()

if set(T) - set(S) != set():
    print(-1)
    exit()

d = defaultdict(list)
l = [0 for _ in range(26)]

for i, v in enumerate(S, 1):
    l[ord(v)-ord('a')] += 1
    d[v].append(i)

len_S = len(S)

# print(l)

ans = 0
c = 0
for t in T:
    i = bisect.bisect_left(d[t], c)
    # print(l[ord(t)-ord('a')])
    if i < l[ord(t)-ord('a')]:
        ans += d[t][i]-c+1
        c = d[t][i]+1
        # print(d[t][i])
    else:
        # print(ans, len_S, c, d[t][0])
        ans += len_S-c+d[t][0]+1
        c = d[t][0]+1
    # print(ans)

if ans > 10**100*len_S:
    print(-1)
else:
    print(ans-1)
### BUGGY CODE ###

def check(li):
    b = 0
    for eb, eh in li:
        if b + eb < 0:
            return False

        b += eh

    return True


n = int(input())
s = [input() for _ in range(n)]

l = []
r = []
sm = 0
for word in s:
    h = 0
    b = 0
    for e in word:
        if e == "(":
            h += 1
        else:
            h -= 1

        b = min(b, h)

    if h > 0:
        l.append([b, h])
    else:
        r.append([b-h, -h])

    sm += h

l.sort(reverse=True)
r.sort(reverse=True)

if check(l) and check(r) and sm == 0:
    ans = "Yes"
else:
    ans = "No"
print(ans)


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]

l = 0
r = 0
m = []


def fin():
    print("No")
    exit()


for word in s:
    stack = []
    for e in word:
        if stack and stack[-1] == "(" and e == ")":
            stack.pop()
        else:
            stack.append(e)

    if stack:
        if stack[0] == ")" and stack[-1] == "(":
            m.append(stack)
        elif stack[0] == ")":
            r += len(stack)
        else:
            l += len(stack)

ml = []
mm = 0
mr = []

for word in m:
    ll = word.index("(")
    rr = len(word) - ll
    if ll > rr:
        mr.append([ll, rr])
    elif ll < rr:
        ml.append([ll, rr])
    else:
        mm = max(mm, ll)

ml.sort()
for ll, rr in ml:
    l -= ll

    if l < 0:
        fin()

    l += rr

mr.sort(key=lambda x: x[1])
for ll, rr in mr:
    r -= rr

    if r < 0:
        fin()

    r += ll

if mm <= l or mm <= r:
    if l == r:
        print("Yes")
        exit()

fin()
### BUGGY CODE ###

from itertools import accumulate
import bisect

N=int(input())
A=[int(x) for x in input().split()]
S=list(accumulate(A))

def solve(x):
  cnt=S[x]
  L=bisect.bisect_left(S,cnt/2)
  R=bisect.bisect_left(S,(cnt+S[N-1])/2)
  L2=bisect.bisect_right(S,cnt/2)
  R2=bisect.bisect_right(S,(cnt+S[N-1])/2)
  res=10**10
  if R!=N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2-1],cnt-S[L2-1],S[R]-cnt,S[N-1]-S[R]]
    res=min(res,max(ans)-min(ans),max(ans2)-min(ans2))
  if R2!=N:
    ans3=[S[L],cnt-S[L],S[R2-1]-cnt,S[N-1]-S[R2-1]]
    ans4=[S[L2-1],cnt-S[L2-1],S[R2-1]-cnt,S[N-1]-S[R2-1]]
    res=min(res,max(ans3)-min(ans3),max(ans4)-min(ans4))
  return res

res=10**10
for i in range(N):
  a=solve(i)
  res=min(res,a)
print(res)

### FIXED CODE ###

from itertools import accumulate
import bisect

N=int(input())
A=[int(x) for x in input().split()]
S=list(accumulate(A))

def solve(x):
  cnt=S[x]
  L=bisect.bisect_left(S,cnt/2)
  R=bisect.bisect_left(S,(cnt+S[N-1])/2)
  L2=L-1
  R2=R-1
  res=10**10
  if R < N:
    ans=[S[L],cnt-S[L],S[R]-cnt,S[N-1]-S[R]]
    ans2=[S[L2],cnt-S[L2],S[R]-cnt,S[N-1]-S[R]]
    res=min(res,max(ans)-min(ans),max(ans2)-min(ans2))
  if R2 < N:
    ans3=[S[L],cnt-S[L],S[R2]-cnt,S[N-1]-S[R2]]
    ans4=[S[L2],cnt-S[L2],S[R2]-cnt,S[N-1]-S[R2]]
    res=min(res,max(ans3)-min(ans3),max(ans4)-min(ans4))
  return res

res=10**10
for i in range(N):
  a=solve(i)
  res=min(res,a)
print(res)
### BUGGY CODE ###

n = int(input())
list_A = list(map(int, input().split()))
list_B = list(set(list_A))
an = 0
for i in range(len(list_B)):
    c = list_A.count(list_B[i])
    an += (c*(c-1))//2


for i in range(n):
    c = list_A.count(list_A[i])
    if c != 2:
        ans = an - (c*(c-1))//2 + ((c-1)*(c-2))//2
    else:
        ans = an - 1
    print(ans)

### FIXED CODE ###

n = int(input())
list_A = list(map(int, input().split()))
list_B = list(set(list_A))
list_M = [0 for _ in range(n+1)]

for s in list_A:
    list_M[s] += 1
total = 0

for i in range(n+1):
    total += list_M[i]*(list_M[i]-1)//2

for s in list_A:
    ans = total - list_M[s] + 1
    print(ans)
### BUGGY CODE ###

n = int(input())
L =[]
for i in range(n):
    x = int(input())
    L.append(x)

m = L[1]-L[0]

for x in range(n-1):

    for i in range(x,n-1):
        m = max([m,L[i+1]-L[x]])

print (m)

### FIXED CODE ###

n = int(input())
L =[]
for i in range(n):
    x = int(input())
    L.append(x)

ma = L[1]-L[0]
mi = L[0]
for x in range(n-1):
    ma = max([ma,L[x+1]-mi])
    mi = min(mi,L[x+1])


print (ma)
### BUGGY CODE ###

import math
N = int(input())
A = list(map(int,input().split()))
A_set = set(A)
ans=N
cut=0
for i in range(len(A_set)):
	comp = A.count(A_set.pop())
	cut+= comp-1
cut = math.ceil(cut/2)*2
print(ans-cut)

### FIXED CODE ###

import math
import collections
N = int(input())
A = list(map(int,input().split()))
A_collections = collections.Counter(A)
ans=N
cut=0
for comp in A_collections.values():
	cut+= comp-1
cut = math.ceil(cut/2)*2
print(ans-cut)
### BUGGY CODE ###

s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))


### FIXED CODE ###

s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

print(dp[len(s)-1][5]%(10**9+7))
### BUGGY CODE ###

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

R = []
G = []
B = []

count = 0
for s in S:
    if s == "R":
        R.append(count)
    elif s == "G":
        G.append(count)
    elif s == "B":
        B.append(count)
    count += 1

def checker(i,E,F):
    wa =0
    EE = [x for x in E if x > i]
    FF = [x for x in F if x > i]
    for e in EE:
        for f in FF:
            if i>e or i > f:
                pass
            else:
                if f > e and e-i != f-e:
                    wa += 1
                elif e > f and f-i != e-f:
                    wa += 1
    return(wa)

goukei = 0
for i in range(N):
    s = S[i]
    if s == "R":
        goukei += checker(i,G,B)
    elif s == "G":
        goukei += checker(i,R,B)
    elif s == "B":
        goukei += checker(i,R,G)

print(goukei)

### FIXED CODE ###

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

nR = 0
nG = 0
nB = 0

for s in S:
    if s == "R":
        nR += 1
    elif s == "G":
        nG += 1
    elif s == "B":
        nB += 1
        
c1pat = nR*nG*nB

mcount = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        k = j + (j-i)
        if k < N:
#             print(i,j,k)
            if set([S[i],S[j],S[k]]) == set(["R","G","B"]):
                mcount += 1
                
                
print(c1pat - mcount)
### BUGGY CODE ###

from math import factorial
n,m,K=map(int,input().split())
ans=0
t=0
def comb(n,r):
    return factorial(n)//factorial(n-r)//factorial(r)
for i in range(3,n+m+1):
    for j in range(1,i):
        if(j>m):
            break
        k=i-j
        if(k<=n):
            if(j==1 or k==1):
                ans+=(i-2)*(m-j+1)*(n-k+1)
            else:
                ans+=(i-2)*(m-j+1)*(n-k+1)*2
print((ans*comb(n*m-2,K-2))%(10**9+7))

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
x=1
y=1
for i in range(1,k-1):
    y*=i
    y%=mod
for i in range(k-2):
    x*=n*m-2-i
    x%=mod
x*=pow(y,mod-2,mod)
x%=mod
def f(n,m):
    s=0
    for i in range(1,n):
        s+=i*(n-i)
        s%=mod
    return s*m*m%mod
print((f(n,m)+f(m,n))*x%mod)
### BUGGY CODE ###

import numpy as np

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

A = np.sort(A)

for i in range(1, N+1):
    ans = np.count_nonzero(A == i)
    print(ans)
    A = A[ans:]

### FIXED CODE ###

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

import collections
c = collections.Counter(A)

for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

ans = input()
q = int(input())

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    #反転
    ans = ''.join(list(reversed(ans)))
  else:
    if int(query[1]) == 1:
      # 先頭
      ans = query[2] + ans
    else:
      # 後方
      ans = ans + query[2]

print(ans)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
num = 0
ans = deque(s)

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:
      if num%2 == 0:
        # 後方
        ans.append(query[2])
      else:
        ans.appendleft(query[2])     

if num%2 == 0:
  print(''.join(ans))
else:
  ans.reverse()
  print(''.join(ans))
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

from itertools import product
inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j, k in product(range(H+1), repeat=2):
        cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
        dp[j+1][k] = min(dp[j+1][k], cost)
        dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

from bisect import bisect_right
N = int(input())
D = list(map(int, input().split()))
D.sort(reverse=False)

count = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        l = D[:N - j - 1]
        ind = bisect_right(D, D[i] + D[j] - 1)
        count += max(ind - j - 1, 0)

print(count)


### FIXED CODE ###

from bisect import bisect_right
N = int(input())
D = list(map(int, input().split()))
D.sort(reverse=False)

count = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        # target = int(D[N - i - 1]) - int(D[N - j - 1])
        # l = D[:N - j - 1]
        # count += len(l) - bisect_right(l, target)
        ind = bisect_right(D, D[i] + D[j] - 1)
        count += max(ind - j - 1, 0)

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

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

m = 30
d = [1<<i for i in range(m+1)]

c = [[] for i in range(m)]
for bi in b:
    for i in range(m):
        c[i].append(bi&(d[i+1]-1))
for i in range(m):
    c[i].sort()

from bisect import bisect_left

keta = [0]*m
for ai in a:
    for i in range(m):
        aj = ai&(d[i+1]-1)
        one1 = bisect_left(c[i], d[i+1]-aj) - bisect_left(c[i],d[i]-aj)
        one2 = n - bisect_left(c[i], d[i+1]+d[i]-aj)
        keta[i] += one1+one2

ans = 0
for i in range(m):
    if keta[i]%2:
        ans += 1<<i

print(ans)

### FIXED CODE ###

# 写経
# https://atcoder.jp/contests/arc092/submissions/5244389

from bisect import bisect_left

INF = float('inf')

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

def calc_bit(k):
    # これ以上の桁は不要
    mod = 1 << (k + 1)
    amod = [a & (mod - 1) for a in A]
    bmod = [b & (mod - 1) for b in B]
    amod.sort()
    bmod.sort()
    ret = 0

    # bmod + amod のうち k ビット目が 1 となる数
    # => (1 << k) 以上 (2 << k) 未満または (3 << k) 以上 (4 << k) 未満
    # しゃくとる
    b01 = bisect_left(bmod, (1 << k) - amod[0])
    b10 = bisect_left(bmod, (2 << k) - amod[0])
    b11 = bisect_left(bmod, (3 << k) - amod[0])
    for a in range(len(amod)):
        while b01 - 1 >= 0 and bmod[b01 - 1] >= (1 << k) - amod[a]:
            b01 -= 1
        while b10 - 1 >= 0 and bmod[b10 - 1] >= (2 << k) - amod[a]:
            b10 -= 1
        while b11 - 1 >= 0 and bmod[b11 - 1] >= (3 << k) - amod[a]:
            b11 -= 1
        # (1 << k) 以上 (2 << k) 未満
        ret += b10 - b01
        # (3 << k) 以上 (4 << k) 未満
        ret += N - b11

    return ret % 2


ans = 0
for i in range(30):
    ans += calc_bit(i) * (1<<i)
print(ans)
### BUGGY CODE ###

n = int(input())
a=[]
for i in range(n):
  j=int(input())
  if j in a:
    a.remove(j)
  else:
    a.append(j)
print(len(a))

### FIXED CODE ###

from collections import Counter 
n=int(input())
a=Counter([int(input()) for _ in range(n)])
ans=0
for i in a.values():
  ans+=i%2
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

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

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

for i in range(0,k):
  if a >= 1:
    a -= 1
  elif b >=1:
    b -= 1
    
print('{} {}'.format(a,b))

### FIXED CODE ###

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

if k >= a:
  _a = 0
  if k-a >= b:
    _b = 0
  else:
    _b = b-(k-a)
else:
  _a = a - k
  _b = b
     
print('{} {}'.format(_a,_b))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
for i in range(1,N+1):
    x=A.count(i)
    print(x)
    A=A[x:]


    









### FIXED CODE ###

import collections

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

for i in range(1,N+1):
    print(c[i])