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

# -*- coding: utf-8 -*-
#尺取り法

from bisect import bisect_left, bisect_right

def main():
    N, K =  [int(i) for i in input().split()]
    A =  sorted(list(map(int, input().split())))

    nega_end = bisect_left(A, 0)
    posi_start = bisect_right(A, 0)

    posi_cnt = N - posi_start
    nega_cnt = nega_end
    zero_cnt = N - (posi_cnt + nega_cnt)

    nega_pairs_cnt = posi_cnt * nega_cnt
    zero_pairs_cnt = zero_cnt * (posi_cnt + nega_cnt) + (zero_cnt * (zero_cnt-1) // 2)

    if K <= nega_pairs_cnt:
        ok, ng = 0, -10 ** 18

        while abs(ok - ng) > 1:

            X = (ok + ng) // 2
            or_higher_cnt, r = 0, posi_start

            for l in range(nega_end):
                while (r < N) and (A[l] * A[r] > X):
                    r += 1
                or_higher_cnt += posi_cnt - (r - posi_start)

            if or_higher_cnt >= K:
                ok = X
            else:
                ng = X
            #print(ok, ng)
        print(ok)

    elif nega_pairs_cnt < K <= nega_pairs_cnt + zero_pairs_cnt:
        print(0)
        return
    else:
        K -= (nega_pairs_cnt + zero_pairs_cnt)
        ok, ng = 10 ** 18, 0
        while abs(ok - ng) > 1:
            X = (ok + ng) // 2
            or_higher_cnt = 0
            r = N - 1
            for l in range(posi_start, N):
                while (r < N) and (A[l] * A[r] > X) and (l < r):
                    r -= 1
                or_higher_cnt += max(0, r - l)

            l = 0
            for r in range(nega_end - 1, -1, -1):
                while (l < N) and (A[l] * A[r] > X) and (l < r):
                    l += 1

                or_higher_cnt += max(0, r - l)

            if or_higher_cnt >= K:
                ok = X
            else:
                ng = X
        print(ok)
if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
#尺取り法

import numpy as np
n, k = map(int,input().split())
a = np.array(list(map(int,input().split())))
a.sort()
posi = a[a>0]
zero = a[a==0]
nega = a[a<0]
#print(posi)
# 2分探索, midより小さいものを数える
l = -10**18-1
r = 10**18+1
while r-l > 1:
    mid = (r+l)//2
    cnt = 0
    if mid >= 0:
        cnt += len(zero)*n

    # a.searchsorted(v, side="left"): a[i-1] < v <= a[i]であるvのindexを返す
    # a.searchsorted(v, side="right"): a[i-1] <= v < a[i]であるvのindexを返す

    cnt += a.searchsorted(mid//posi, side="right").sum()
    cnt += (n - a.searchsorted(-(-mid//nega), side="left")).sum()
    cnt -= np.count_nonzero(a*a <= mid)
    cnt //= 2
    #print("mid:", mid)
    #print("mid//posi:", mid//posi)
    #print("search:", a.searchsorted(mid//posi,side="right"))
    #print("-(-mid//nega):", -(-mid//nega))
    #print("search:", a.searchsorted(-(-mid//nega),side="left"))
    #print("nonzero_count:", np.count_nonzero(a*a<=mid))
    #print("count:", cnt)
    #print('-' * 20)
    if cnt >= k:
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

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

a = []

for j in range(1, n-1):
    sj = s[j]
    i = j - 1
    while i > -1:
        if sj != s[i]:
           a.append((i, j)) 
        i -= 1

ans = 0
for (i, j) in a:
    si = s[i]
    sj = s[j]
    for k in range(j + 1, n):
        if j - i == k - j:
            continue
        if si == s[k] or sj == s[k]:
            continue
        ans += 1

print(ans)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(n):
    for d in range(1, n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1

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

N=int(input())
if N%2==0:
  print(N//2,N,N)
else:
  for i in range(1,3501):
    for j in range(1,3501):
      if 4*i*j-N*i-N*j!=0:
        w=(N*i*j)/(4*i*j-N*i-N*j)
        if w>0 and w.is_integer():
          print(i,j,int(w))
          exit()

### FIXED CODE ###

N=int(input())
if N%2==0:
  print(N//2,N,N)
else:
  for i in range(1,3501):
    for j in range(1,3501):
      if 4*i*j-N*i-N*j!=0:
        w=(N*i*j)/(4*i*j-N*i-N*j)
        if w>0 and w.is_integer():
          print(i,j,int(w))
          exit()
### BUGGY CODE ###

import itertools
n = int(input())
s = [i for i in input()]
p = set()
for v in itertools.combinations(s, 3):
  if v[0]+v[1]+v[2] not in p:
    p.add(v[0]+v[1]+v[2])
print(len(p))

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
    a = s.find(str(i))
    if a == -1: continue
    for j in range(10):
        b = s.find(str(j), a+1)
        if b == -1: continue
        for k in range(10):
            if s.find(str(k), b+1) != -1:
                ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j < a[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j-a[i]] + b[i])
    return min(dp[N][H:Hmax+1])


H, N = map(int,input().split())
a = [0] * N
b = [0] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())
Hmax = H + max(a)
INF = 10**9
dp = np.full((N+1,Hmax+1), INF, dtype=int)
dp[0][0] = 0
print(rec_z())

### FIXED CODE ###

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())
### BUGGY CODE ###

N, W = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(N)]
x.insert(0, [0, 0])
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for sum_m in range(1, W+1):
        #品物(w[i], v[i])を選ぶとき
        if sum_m >= x[i][0]:
            dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m-x[i][0]] + x[i][1])
        #品物(w[i], v[i])を選ばないとき
        dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m])
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(N)]
x.insert(0, [0, 0])
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for sum_m in range(1, W+1):
        #品物(w[i], v[i])を選ぶとき
        if sum_m >= x[i][0]:
            dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m-x[i][0]] + x[i][1])
        #品物(w[i], v[i])を選ばないとき
        dp[i][sum_m] = max(dp[i][sum_m], dp[i-1][sum_m])
print(dp[N][W])
### BUGGY CODE ###

a=int(input())
for i in range(a):
	p=a//(i+1)
	if (i+1)>=p and a%(i+1)==0:
		break
print(i+p-1)

### FIXED CODE ###

n=int(input())
i=0
s=[]
p=0
for i in range(int(n**0.5)):
    i+=1
    if n%i==0:
        p=1
        s.append(n//i+i-2)
print(min(s))
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
R = sorted(set(A))

ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    for j in range(N):
        if A[j] < R[i]:
            temp += sorted(temp2)[:min(len(temp2),max(0,len(temp2) - K + 1))]
            temp2 = []
        else:
            temp2.append(A[j])
    temp += sorted(temp2)[:min(len(temp2),max(0,len(temp2) - K + 1))]

    temp = sorted(temp)
    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)
    


### FIXED CODE ###

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            if l >= K:
                temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    if l >= K:
        temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
mod = 998244353
MAX_N = 2 * (10**5)

fact = [1]
fact_inv = [0] * (MAX_N + 4)

for i in range(MAX_N + 3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod

def cmb(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

ans = 0
col = M

for k in range(N-1, -1, -1):
    now = col
    now *= cmb(N-1,k,mod)
    if k <= K:
        ans += now
    ans %= mod
    col *= M-1

print(ans)



### FIXED CODE ###

N, M, K = map(int, input().split())
mod = 998244353

fact = [1 for i in range(N+1)]
fact_inv = [1 for i in range(N+1)]

for i in range(1, N+1):
    fact[i] = fact[i-1] * i % mod
    fact_inv[i] = pow(fact[i], mod-2, mod)

def cmb(n,k):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

ans = 0

for k in range(K+1):
    now = M * pow(M-1, N-k-1, mod) * cmb(N-1,k)
    ans = (ans + now % mod) % mod

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

import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    r, g, b, n = ns()
    ans = 0
    for i in range(n // r + 1):
        for j in range(n // g + 1):
            tmp = n - r * i - g * j
            if tmp % b == 0 and tmp > -1:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools

import copy

# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    r, g, b, n = ns()
    ans = 0
    for i in range(n // r + 1):
        for j in range(n // g + 1):
            tmp = n - r * i - g * j
            if tmp % b == 0 and tmp > -1:
                ans += 1
    print(ans)


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

n,m=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
l=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*m]
s=[0]*n
i=1
for x in l:
    if s[x[0]]==s[x[1]]==0:
        s[x[0]]=i
        s[x[1]]=i
        i+=1
    elif s[x[0]]==s[x[1]]>0:
        pass
    elif s[x[0]]==0:
        s[x[0]]=s[x[1]]
    elif s[x[1]]==0:
        s[x[1]]=s[x[0]]
    else:
        t=s[x[1]]
        for j in range(n):
            if s[j]==t:s[j]=s[x[0]]
list=list(set(s))
ans=0
if 0 in list:
    for j in range(n):
        if s[j]==0 and p[j]==j:ans+=1
    list.remove(0)
for j in list:
    ans+=len(set([p[k] for k in range(n) if s[k]==j])&set([k for k in range(n) if s[k]==j]))
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
uf=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    uf.union(x,y)
ans=0
for i in range(n):
    if uf.same_check(i+1,p[i]):ans+=1
print(ans)
### BUGGY CODE ###

import sys
import math
import itertools

input = sys.stdin.readline


def main():
    l, r = [int(i) for i in input().split()]
    num = set(list([i % 2019 for i in range(l, r + 1)]))
    min_ = 2019
    for i, j in itertools.combinations(num, 2):
        min_ = min([i * j % 2019, min_])
        if min_ == 0:
            break
    print(min_)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math
import itertools

input = sys.stdin.readline


def main():
    l, r = [int(i) for i in input().split()]

    if r - l >= 2019:
        print(0)
        return
    else:
        num = [i for i in range(l, min(l + 2019, r + 1))]
        min_ = 2019
        for i, n in enumerate(num):
            for j in num[i + 1 :]:
                min_ = min([n * j % 2019, min_])
    print(min_)


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

import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = []
c = np.zeros(N)
ans = 0
for i in reversed(range(1, N+1)):
    if (a[i-1] % 2 == 0 and c[i-1]%2 == 1) or (a[i-1] % 2 == 1 and c[i-1]%2 == 0):
        b.append(i)
        ans += 1
        for j in range(1,N+1):
            if i%j == 0:
                c[j-1] += 1

print(ans)
if ans != 0:
    print(*b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

b=[]
M = 0
count = [0 for _ in range(N+1)]
for i in reversed(range(1,N+1)):
    if count[i]%2 == a[i-1]: continue
    else:
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                count[j]+=1
                if j!=i//j:
                    count[i//j]+=1
        M+=1
        b.append(i)
print(M)
if M!=0:
    print(*b)
### BUGGY CODE ###

N = int(input())
graph = []
for _ in range(N):
	graph.append(list(map(int, input().strip())))

def check(graph):
	queue = [0]
	dists = [None] * N
	dists[0] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None:
					dists[i] = dist
					queue.append(i)
				else:
					if d % 2 != dist %2:
						return False
					elif d > dist:
						dists[i] = dist
						queue.append(i)
	return True

def search(graph, start):
	queue = [start]
	dists = [None] * N
	dists[start] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None or d > dist:
					dists[i] = dist
					queue.append(i)
	return max(dists)

if check(graph):
	diam = 0
	for i in range(N):
		d = search(graph, i)
		if d > diam:
			diam = d
	print(diam + 1)
else:
	print(-1)


### FIXED CODE ###

N = int(input())
graph = []
for _ in range(N):
	graph.append(list(map(int, input().strip())))

def check(graph):
	queue = [0]
	dists = [None] * N
	dists[0] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None:
					dists[i] = dist
					queue.append(i)
				else:
					if d % 2 != dist %2:
						return False
					elif d > dist:
						dists[i] = dist
						queue.append(i)
	return True

def search(graph, start):
	queue = [start]
	dists = [None] * N
	dists[start] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None or d > dist:
					dists[i] = dist
					queue.append(i)
	return max(dists)

if check(graph):
	diam = 0
	for i in range(N):
		d = search(graph, i)
		if d > diam:
			diam = d
	print(diam + 1)
else:
	print(-1)
### BUGGY CODE ###

import itertools
import sys
from typing import Callable, NoReturn, Tuple


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline
    n, k = map(int, readline().rstrip().split())  # type: int,...
    p: Tuple[int] = tuple(int(_) for _ in readline().rstrip().split())

    answer: int = min(tuple(sum(fruits) for fruits in itertools.combinations(p, k)))
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import sys
from typing import Callable, List, NoReturn


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline
    n, k = map(int, readline().rstrip().split())  # type: int,...
    p: List[int] = [int(_) for _ in readline().rstrip().split()]
    p.sort()
    print(sum(p[:k]))


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

x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())),reverse = True)
q = sorted(list(map(int, input().split())),reverse = True)
r = sorted(list(map(int, input().split())),reverse = True)


ans = 0

while (p[0] > r[0]):
    ans += p.pop(0)
    x -= 1
    if (x == 0):
        break
while (q[0] > r[0]):
    ans += q.pop(0)
    y-=1
    if (y == 0):
        break

if (x == 0 and y == 0):
    print(ans)
else:
    aps = sorted(p[0: x] + q[0: y] + r[0: x + y], reverse=True)
    #print(aps)
    print(ans+sum(aps[0:x+y]))



### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())),reverse = True)
q = sorted(list(map(int, input().split())),reverse = True)
r = sorted(list(map(int, input().split())),reverse = True)

px = p[:x]
qx = q[:y]

aps = sorted(px + qx + r, reverse=True)

print(sum(aps[0:x+y]))
### BUGGY CODE ###

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

li = list()
for i, n in enumerate(A):
    li.append((i + 1, n))

li.sort(key=lambda x: x[1])
ans = ""
for y in li:
    ans = ans.__add__(str(y[0]) + " ")

print(ans.strip())

### FIXED CODE ###

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

li = sorted( enumerate(A, 1), key=lambda x: x[1])

print(" ".join([str(i[0]) for i in li]))
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]
    s = [1]*(n+1)

    if 1 in a:
        s[1] = 0

    for i in range(n-1):
        if i+2 in a:
            s[i+2] = 0
            continue
        s[i+2] = (s[i+1] + s[i]) % (10**9+7)

    print(s[-1])

main()

### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])
### BUGGY CODE ###

N = int(input())

NList = list(map(int, input().split()))

result = 1
for i in range(N):
    result *= NList[i]

if result > 10 ** 18:
    print('-1')
else:
    print(result)

### FIXED CODE ###

N = int(input())

NList = list(map(int, input().split()))

NList.sort()
result = 1
for i in range(N):
    result *= NList[i]

    if result > 10 ** 18:
        break

if result > 10 ** 18:
    print('-1')
else:
    print(result)
### BUGGY CODE ###

# coding:utf-8

import math


INF = float('inf')


def inpl(): return list(map(int, input().split()))


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

E = [2 * (i + 1) + 1 for i in range(N)]
E[0] = 5

ans = INF
for k in range(1, N + 1):
    tmp = 0
    for i in range(1, N + 1, k):
        if N + 1 - i - k < 0:
            tmp += E[math.ceil(i / k) - 1] * (B[N - i + 1])
        else:
            tmp += E[math.ceil(i / k) - 1] * (B[N - i + 1] - B[N - i - k + 1])
        # print(k, i, tmp)

    ans = min(ans, tmp + (N + k) * X)
    # print(ans)

print(ans)

### FIXED CODE ###

# coding:utf-8


INF = float('inf')


def inpl(): return list(map(int, input().split()))


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

ans = INF
for k in range(1, N + 1):
    e = 5
    cur = N - k
    tmp = e * (B[N] - B[cur]) + (N + k) * X
    cur -= k
    while True:
        tmp += e * (B[cur + k] - B[max(cur, 0)])
        if cur <= 0:
            break
        e += 2
        cur -= k

    ans = min(ans, tmp)

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

s=input()
qnum=int(input())
q=[input().split() for i in range(qnum)]
for i in q:
  if i[0]=="1":
    s=s[::-1]
  else:
    if i[1]=="1":
      s=i[2]+s
    else:
      s=s+i[2]
print(s)

### FIXED CODE ###

s=input()
n=int(input())
t=""
for _ in range(n):
  q=input().split()
  if q[0]=="1":
    t,s=s,t
  else:
    if q[1]=="1":
      t+=q[2]
    else:
      s+=q[2]
t=t[::-1]
print(t+s)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def ncr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

numList = [0] * (n+1)
numSet = set()

resultList = [0] * (n+1)
resultSet = set()

for i in range(len(a)):
    numList[a[i]] += 1
    if(numList[a[i]]==2):
        numSet.add(a[i])

for i in range(len(a)):
    if(a[i] in resultSet):
        print(resultList[a[i]])
        continue
    s = 0
    for j in numSet:
        if(j == a[i]):
            if(numList[j]>2):
                s += ncr(numList[j]-1,2)
        else:
            s += ncr(numList[j],2)
    print(s)
    resultList[a[i]] = s
    resultSet.add(a[i])

    


### FIXED CODE ###

from operator import mul
from functools import reduce

def ncr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

numList = [0] * (n+1)
numSet = set()

ncrList = [0] * (n+1)

resultList = [0] * (n+1)
resultSet = set()

for i in range(len(a)):
    numList[a[i]] += 1
    if(numList[a[i]]==2):
        numSet.add(a[i])

sums = 0
for i in numSet:
    ncrList[i] = ncr(numList[i], 2)
    sums += ncrList[i]

for i in range(len(a)):
    if(a[i] in resultSet):
        print(resultList[a[i]])
        continue
    s = sums
    if(a[i] in numSet):
        if(numList[a[i]] == 2):
            s -= 1
        else:
            s -= ncrList[a[i]]
            s += ncr(numList[a[i]]-1, 2)
    print(s)
    resultList[a[i]] = s
    resultSet.add(a[i])
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
ship_list = list()
way_list = list()
for i in range(M):
    a, b = map(int, input().split())
    ship_list.append((a, b))
    if b == N:
        way_list.append(a)

for dest in ship_list:
    if dest[0] == 1:
        if dest[1] in way_list:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

def data_input():
    D = int(input())
    C = tuple(map(int, input().split()))

    S = []
    for i in range(D):
        s = tuple(map(int, input().split()))
        S.append(s)

    return D, C, S


def score(D, C, S, T):
    """入力D, C, Sと出力Tからスコアを計算する関数"""

    last = [0] * 26  # 0で初期化されている

    def decrease(d, last):
        """d日めにiを開催した時の満足度の減少を返す関数"""
        res = 0
        for i in range(26):
            ith = C[i] * (d+1 - last[i])
            res -= ith
        return res

    v = 0
    for d, i in enumerate(T):
        last[i] = d + 1
        v += S[d][i] + decrease(d, last)
    return v

D, C, S = data_input()
T = []
for d in range(D):
    local_max = 0
    for i in range(26):
        if score(d, C, S, T+[i]) >= local_max:
            max_i = i
            local_max = score(d, C, S, T+[i])
            # print(f'local_max at {d}-day is updated to {local_max}')
    T.append(max_i)

v = score(D, C, S, T)

for t in T:
    print(t+1)

### FIXED CODE ###

D = 365

for i in range(D):
  print(1)