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

import sys
sys.setrecursionlimit(1000000000)
from collections import OrderedDict
def key(x, y):
    return str(x)+str(y)
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    # M = []
    # for i in range(N):
    #     M.append([j for j in range(N-i)])
    M = OrderedDict()
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    # print(M)
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            # print('cost before after', M[key(x,y)], from_cost+1)
            if M[key(x,y)] >= from_cost+1:
                # print('key', key(x,y), '->', from_cost+1)
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    # M[key(X,Y)] = min(M[key(X,Y)], 1)
    # print(M)
    helper(X, Y, 0)

    cost_list = list(M.values())
    # print(cost_list)
    for k in range(N-1):
        print(cost_list.count(k+1))


main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
from collections import Counter
def key(x, y):
    return str(x)+str(y)
def main2():
    # TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    M = {}
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            if M[key(x,y)] > from_cost+1:
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    helper(X, Y, 0)

    cost_list = Counter(list(M.values()))
    for k in range(N-1):
        print(cost_list[k+1])

from collections import deque
INF = 1e10


def main3():
    # official TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    ans = [0 for _ in range(N)]
    for sv in range(N):
        dist = [INF for _ in range(N)]
        q = deque([])

        def push(v, d):
            if dist[v] != INF: return
            dist[v] = d
            q.append(v)

        push(sv, 0)

        while q:
            sv = q.popleft()
            d = dist[sv]
            if sv > 0:
                push(sv-1, d+1)
            if sv < N-1:
                push(sv+1, d+1)
            if sv == X:
                push(Y, d+1)
            if sv == Y:
                push(X, d+1)

        for d in dist:
            ans[d] += 1
    
    for k in range(1, N):
        print(ans[k] // 2)

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    dist = [0 for _ in range(N)]
    for i in range(N-1):
        for j in range(i+1, N):
            d = min(abs(X-i)+1+abs(j-Y), abs(i-j), abs(Y-i)+1+abs(j-Y))
            dist[d] += 1
    
    for k in range(1, N):
        print(dist[k])
 

main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
C = 1
for i in range(N):
  C *= A[i]
if C <= 10**18:
  print(C)
else:
  print('-1')

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
C = 1
for i in range(N):
  C *= A[i]
  if C > 10**18:
    print('-1')
    break
  elif A[i]==0:
    break
if C <= 10**18:
  print(C)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    ans = -1
    for n in range(M)[N:]:
        for i in range(M + 1)[n + 1:]:
            mod = n * i % 2019
            if ans < 0 or mod < ans:
                ans = mod
        if mod == 0:
            break
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    ans = -1
    for n in range(M)[N:]:
        for i in range(M + 1)[n + 1:]:
            mod = n * i % 2019
            if ans < 0 or mod < ans:
                ans = mod
                if ans == 0:
                    break
        if ans == 0:
            break
    print(ans)


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

n = int(input())
list = list(map(int,input().split(" ")))
result = n
for i in range(1,n):
    for j in range(i):
        if list[i] > list[j]:
            result -= 1
            break
print(result)

### FIXED CODE ###

n = int(input())
list = list(map(int,input().split(" ")))
result = n
tem = list[0]
for i in range(n):
    if tem >= list[i]:
        tem = list[i]
    else:
        result -= 1

print(result)
### BUGGY CODE ###

N=int(input())
tlist=[]
alist=[]
dlist=[]

for i in range(0,N):
    t,a=map(int,input().split(" "))
    d=t+a
    tlist.append(t)
    alist.append(a)
    dlist.append(d)
#print(tlist,alist,dlist)

count=0
tscore=0
ascore=0
number=0

for count in range(0,N):
    if count%2==0:
        number=dlist.index(max(dlist))
        tscore+=tlist[number]
    else:
        number=dlist.index(max(dlist))
        ascore+=alist[number]

    #print(tscore,ascore)
    del tlist[number]
    del alist[number]
    del dlist[number]      

print(tscore-ascore)


### FIXED CODE ###

N=int(input())
flist=[]

for i in range(0,N):
    t,a=map(int,input().split(" "))
    d=t+a
    flist.append([d,t,a])
#print(flist)

count=0
score=0
number=0
flist.sort(reverse=True)
#print(flist)

for count in range(0,N):
    if count%2==0:
        score+=flist[count][1]
    else:
        score-=flist[count][2]

    #print(score)
print(score)
### BUGGY CODE ###

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

B=[]
C=[]
for i,a in enumerate(A):
  B.append(a-i)
  C.append(-a-i)
ans=0
for b in B:    
  ans+=C.count(b)
print(ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
A=list(map(int,input().split()))
B=[]
C=[]
for i,a in enumerate(A):
  B.append(i+a)
  C.append(i-a)
  
b = Counter(B)
c = Counter(C)
ans=0
for d in b.items():
  ans+=d[1]*c[d[0]]
print(ans)
### BUGGY CODE ###

N,K = map(int, input().split())
V = list(map(int, input().split()))
from collections import deque
d=deque(V)
my_gem = []
max_value=-1000000000
def nxt(num,cur_v):
        global max_value
        global my_gem
        if num == K :
                return

        if len(d) > 0:

                # sousa A
                gem_v = d.popleft()
                cur_v+=gem_v
                if max_value < cur_v:
                        max_value = cur_v

                my_gem.append(gem_v)
                nxt(num+1,cur_v)

                my_gem.remove(gem_v)
                cur_v -= gem_v
                d.appendleft(gem_v)

                # sousa B
                gem_v = d.pop()
                cur_v+=gem_v
                if max_value < cur_v:
                        max_value = cur_v

                my_gem.append(gem_v)
                nxt(num+1,cur_v)
                my_gem.remove(gem_v)

                cur_v -= gem_v
                d.append(gem_v)

        # sousa C
        itr = 0
        for pushgem in my_gem:
                itr+=1
                my_gem.remove(pushgem)
                cur_v -= pushgem

                if max_value < cur_v:
                        max_value = cur_v

                d.appendleft(pushgem)
                nxt(num+1,cur_v)
                d.popleft()

                cur_v += pushgem
                my_gem.append(pushgem)
                if itr == len(my_gem):
                        break

        # sousa D
        itr = 0
        for pushgem in my_gem:
                my_gem.remove(pushgem)
                cur_v -= pushgem

                if max_value < cur_v:
                        max_value = cur_v

                d.append(pushgem)
                nxt(num+1,cur_v)
                d.pop()

                cur_v += pushgem
                my_gem.append(pushgem)
                if itr == len(my_gem):
                        break

nxt(0,0)
print(max_value)

### FIXED CODE ###

N,K = map(int, input().split())
V = list(map(int, input().split()))
import sys
max_value=-1000000000

for i in range(K+1):
        for left in range(i+1):
                right= i - left

                leftlist = V[:left]

                if right == 0:
                        rightlist = []
                else:
                        rightlist = V[-right:]

        #       print(left)
        #       print(right)


                leftlist.extend(rightlist)

                leftlist.sort()


#               for push in range(K-i):

                num = 0
                for value in range(len(leftlist)):
                        num+=1
                        if num > K-i:
                                break

                        if leftlist[value] > 0:
                                break
                        leftlist[value]=0
        #       print(leftlist)



                s = sum(leftlist)
                if max_value < s:
                        max_value = s

                if left+right > N:
                        print(max_value)
                        sys.exit()

print(max_value)
### BUGGY CODE ###

import copy

N = int(input())
A = []
B = []

for _ in range(N):
    putin = int(input())
    A.append(putin)
    B.append(putin)

for i in range(N):
    A = copy.deepcopy(B)
    del A[i]
    print(max(A))

### FIXED CODE ###


import numpy as np

N = int(input())
A = []
B = []

for _ in range(N):
    putin = int(input())
    A.append(putin)
    B.append(putin)

MAX = int(np.max(A))
A.remove(MAX)
MAX2 = int(np.max(A))

for i in range(N):
    if B[i] == MAX:
        print(MAX2)
    
    else:
        print(MAX)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
s = [list(map(str, input().rstrip())) for _ in range(h)]

cost = [[10001] * w for _ in range(h)]

if s[0][0] == "#":
    cost[0][0] = 1
else:
    cost[0][0] = 0

q = deque([[0, 0]])
moves = [[1, 0], [0, 1]]

while q:
    curr = q.popleft()
    curr_cost = cost[curr[0]][curr[1]]

    for m in moves:
        y, x = curr[0] + m[0], curr[1] + m[1]
        if y < h and x < w:
            if s[y][x] == "#":
                cost[y][x] = min(curr_cost + 1, cost[y][x])
            else:
                cost[y][x] = min(curr_cost, cost[y][x])
            q.append([y, x])
        else:
            continue

print(cost[-1][-1])

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
s = [list(map(str, input().rstrip())) for _ in range(h)]

dp = [[10001] * w for _ in range(h)]

if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

moves = [[1, 0], [0, 1]]

for y in range(h):
    for x in range(w):
        for m in moves:
            ny, nx = y + m[0], x + m[1]
            if ny >= h or nx >= w:
                continue
            add = 0
            # .から#に突入する時だけカウントが増える
            if s[y][x] == "." and s[ny][nx] == "#":
                add = 1
            dp[ny][nx] = min(dp[ny][nx], dp[y][x] + add)

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

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ok = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit(0)
            elif A[i][j] == A[i][k] + A[k][j]:
                ok = False
        if ok:
            ans += A[i][j]

print(ans)


### FIXED CODE ###

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ok = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit(0)
            elif A[i][j] == A[i][k] + A[k][j]:
                ok = False
        if ok:
            ans += A[i][j]

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

n, m = map(int, input().split(' '))
for i in range(m):
    l, r = map(int, input().split(' '))
    a = set(j for j in range(l, r+1))
    if i == 0:
        result = a
    else:
        result = result & a
print(len(list(result)))

### FIXED CODE ###

n, m = map(int, input().split(' '))
l_ = []
r_ = []
for i in range(m):
    l,r = map(int, input().split(' '))
    l_ += [l]
    r_ += [r]
l = max(l_)
r = min(r_)
if n < l:
    print(0)
elif n < r:
    r = n
    print(r - l + 1)
elif l > r:
    print(0)
elif l == r:
    print(1)
else:
    print(r - l + 1)
### BUGGY CODE ###

k = int(input())
num = input().split()

ass = 0

for i in range(k):
    for j in range(i+1,k):
        n1 = int(num[i]) % (10**9 + 7)
        n2 = int(num[j]) % (10**9 + 7)
        n3 = n1 * n2
        ass += n3
    ass = ass % (10**9 + 7)


ans = ass % (10**9 + 7)
print(ans)

### FIXED CODE ###

k = int(input())
num = input().split()

l = 0
ass = 0
ans = 0

for i in range(k):
    l += int(num[i])

for i in range(k):
    l -= int(num[i])
    ass += int(num[i]) * l
    

ans = ass % (10**9 + 7 )
print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
p = tuple(map(int,input().split()))
count = 0
MaxSum = 0
for _ in p:
    tmp_SumSlice = sum(p[count:count + K])
    if MaxSum < tmp_SumSlice:
        MaxSum = tmp_SumSlice
    count += 1 
print((MaxSum+K)/2)

### FIXED CODE ###

N, K = map(int,input().split())
p = tuple(map(int,input().split()))
MaxSum = sum(p[:K])
tmp_SumSlice = MaxSum
for i in range(K, N):
    tmp_SumSlice = tmp_SumSlice + p[i] - p[i - K]
    if MaxSum < tmp_SumSlice:
        MaxSum = tmp_SumSlice
print((MaxSum+K)/2)
### BUGGY CODE ###

import sys

def findminsum(lst,K,N):
    inf=10**10
    dp=[[(inf if lst[0]<s and j==0 else lst[0]) for j in range(N)] for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    nn=0
    for i in range(N):
        if cards[i]<K:
            c=cards[i]
            cards[i]=0
            if findminsum(cards,K-c,N)>=K:
                nn+=1
            cards[i]=c
    print(nn)

if __name__=='__main__':
    main()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

from itertools import accumulate

def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans *= (n + 1 - i) * pow(i,MOD-2,MOD)
        ans %= MOD
    return ans

def mod_factorial(n):
    value = 1
    for i in range(n,0,-1):
        value*=i
        value%=MOD
    return value

def solve(N: int, K: int, A: "List[int]"):
    A.sort()
    n = N-1
    r = K-1
    # nCkTable[i] = iCr
    nCkTable = [0]*(n+1)

    start = 1
    for _ in range(r):
        start *= n
        start %= MOD
        n -= 1

    bunbo = mod_factorial(r)
    bunbo_gyakugen = pow(bunbo,MOD-2,MOD)

    n = N-1
    for i in range(n, r-1, -1):
        nCkTable[i] = start*bunbo_gyakugen%MOD
        start*=pow(i,MOD-2,MOD)
        start*=i-r

    answer = 0
    for i in range(N):
        answer += A[i]*nCkTable[i]-A[i]*nCkTable[N-1-i]
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

from itertools import accumulate

def mod_factorial(n):
    value = 1
    for i in range(n,0,-1):
        value*=i
        value%=MOD
    return value

def solve(N: int, K: int, A: "List[int]"):
    A.sort()
    n = N-1
    r = K-1
    # nCkTable[i] = iCr
    nCkTable = [0]*(n+1)

    start = 1
    for _ in range(r):
        start *= n
        start %= MOD
        n -= 1

    bunbo = mod_factorial(r)
    bunbo_gyakugen = pow(bunbo,MOD-2,MOD)

    n = N-1
    for i in range(n, r-1, -1):
        nCkTable[i] = start*bunbo_gyakugen%MOD
        start*=pow(i,MOD-2,MOD)
        start*=i-r
        start%=MOD

    answer = 0
    for i in range(N):
        answer += A[i]*(nCkTable[i]-nCkTable[N-1-i])
        answer%=MOD
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    d = set()
    while True:
        d.add(index)
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
            continue
        if index+1 in d:
            print(index+1)
            break
        index, min_i = (index+1 + max_i)//2, index+1

### FIXED CODE ###

import math
N, K = map(int, input().split())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))[::-1]
Cs = [a*b for a, b in zip(As, Bs)]
BCs = list(zip(Bs, Cs))

def func(target):
    r = 0
    for b, c in BCs:
        r += math.ceil(max(0, c - target) / b)
    return r <= K

if __name__ == '__main__':
    min_i, max_i, index = 0, max(Cs)+1, 1
    while True:
        if func(index):
            index, max_i = (index-1 + min_i)//2, index-1
        else:
            index, min_i = (index+1 + max_i)//2, index+1
        if min_i > max_i:
            print(min_i)
            break
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
for i in range(1000):
    C = [i//100, i//10%10, i%10]
    f = 0
    for s in S:
        if int(s) == C[f]:
            f += 1
        if f == 3:
           break
    if f == 3:
        cnt += 1
    if cnt ==1000:
        break
print(cnt)


### FIXED CODE ###

# sumitb2019_d.py
'''
重複考えないとどうなるか
-> 単に nC3 個( N 個から 3 つ選び出す順列と同じ)
というところまで考えたが、結局わからず解説AC
重複を考えるとかなり厳しいので重複がないものに着目する。
（今回であれば 000~999 までのパスワード）
発想の転換が凄い。これ思いつくの天才だろ…。
'''
N = int(input())
S = input()
cnt = 0
for i in range(1000):
    C = [str(i//100), str(i//10%10), str(i%10)]
    f = 0
    for s in S:
        if s == C[f]:
            f += 1
        if f == 3:
           break
    if f == 3:
        cnt += 1
    if cnt ==1000:
        break
print(cnt)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

def steps(n):
    if memo[n] != -1:
        return memo[n]
    if n-1 not in broken:
        one = memo[n-1] if memo[n-1] != -1 else steps(n-1)
    else:
        one = 0
        
    if n-2 not in broken:
        two = memo[n-2] if memo[n-2] != -1 else steps(n-2)
    else:
        two = 0
    
    memo[n] = one + two
    return memo[n]

n, m = map(int, input().split())
broken = [int(input()) for i in range(m)]
memo = [-1 for i in range(n+1)]
memo[0] = 1
memo[1] = 1

print(steps(n) % (10**9+7))

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

def steps(n):
    if memo[n] != -1:
        return memo[n]
    
    one = memo[n-1] if memo[n-1] != -1 else steps(n-1)    
    two = memo[n-2] if memo[n-2] != -1 else steps(n-2)

    memo[n] = one + two
    return memo[n]

n, m = map(int, input().split())
broken = [int(input()) for i in range(m)]
memo = [-1 for i in range(n+1)]
memo[0] = 1
memo[1] = 1
for b in broken:
    memo[b] = 0

print(steps(n) % (10**9+7))
### BUGGY CODE ###

r, g, b, n = map(int,input().split())
cnt = 0
for i in range(n+1):
    for j in range(n+1):
        if ((n - ((i*r) + j*g)) % b == 0) and ((n - ((i*r) + (j*g))) >= 0) :
            #print(n - (i*r) + (j*g))
            cnt += 1
print(cnt)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
cnt = 0
for i in range(n+1):
    for j in range(n+1):
        if ((n - (r*(i) + g*(j))) >= 0) and ((n - (r*(i) + g*(j))) % b == 0):
            cnt += 1
            #print(i)
            #print(j)
print(cnt)
### BUGGY CODE ###

import collections
N = int(input())
S_list = []
for i in range(N):
  S_list.append(input())
 
c = collections.Counter(S_list)
 
words = []
counter = 0
 
 
while(True):
  words.append(c.most_common()[counter][0])
  try:
    if c.most_common()[counter][1] == c.most_common()[counter+1][1]:
      counter += 1
    else:
      break
  except:
    break
 
words = sorted(words)
for j in range(len(words)):
  print(words[j])

### FIXED CODE ###

import collections
N = int(input())
S_list = []
for i in range(N):
  S_list.append(input())

c = collections.Counter(S_list)

d = c.most_common() 

keys = [k for k, v in c.items() if v == d[0][1]]

keys = sorted(keys)

for i in keys:
  print(i)
### BUGGY CODE ###

import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []
for i in range(2, f+1):
    if f % i != 0:
        continue
    else:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
print(len(kouyakusuu)+1)

### FIXED CODE ###

import fractions

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

f = fractions.gcd(A, B)

kouyakusuu = []

if f % 2 == 0:
    kouyakusuu.append(2)
    while f % 2 == 0:
        f = f / 2

i = 3
while i*i <= f:
    if f % i == 0:
        kouyakusuu.append(i)
        while f % i == 0:
            f = f / i
    i += 2
if f != 1:
    kouyakusuu.append(f)
print(len(kouyakusuu)+1)
### BUGGY CODE ###

"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9

N, *P = map(int, read().split())
ans = 0
for i in range(1, len(P)+1):
    if min(P[:i]) == P[:i][-1]:
        ans += 1
print(ans)


### FIXED CODE ###

"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9

N = int(readline())

P = np.array(readline().split(), np.int32)
Q = np.minimum.accumulate(P)
ans = np.count_nonzero(P <= Q)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
answer = [-1] * N
p = []
for i in range(N):
  count[i]  = A.count(i + 1)
  
#nanimo = 0 
#for i in range(N):
#  nanimo += count[j] * (count[j] - 1) // 2

for i in range(N):
  if answer[A[i] - 1] != -1:
    p.append(answer[A[i] - 1])
  else:
    count[A[i] - 1] -= 1
    s = 0
    for j in range(N):
      s += count[j] * (count[j] - 1) // 2
    p.append(s)
    answer[A[i] - 1] = s
    count[A[i] - 1] += 1

for i in p:
  print(i)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
for i in range(N):
  count[A[i] - 1]  += 1
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)