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

from itertools import combinations
n, k = map(int, input().split())
xy = []
xx = []
yy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
    xx.append(x)
    yy.append(y)
xx.sort()
yy.sort()
ans = 10**20
for x1, x2 in combinations(xx, 2):
    for y1, y2 in combinations(yy, 2):
        tmp = 0
        for x, y in xy:
            if x1<=x<=x2 and y1<=y<=y2:
                tmp += 1
        if tmp<k:
            continue
        ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

### FIXED CODE ###

from itertools import combinations
n, k = map(int, input().split())
xy = []
xx = []
yy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append((x, y))
    xx.append(x)
    yy.append(y)
xx.sort()
yy.sort()
ans = 10**20
for x1, x2 in combinations(xx, 2):
    for y1, y2 in combinations(yy, 2):
        tmp = 0
        for x, y in xy:
            if x1<=x<=x2 and y1<=y<=y2:
                tmp += 1
        if tmp<k:
            continue
        ans = min(ans, (x2-x1)*(y2-y1))
print(ans)
### BUGGY CODE ###

import math
K = int(input())

ans = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += math.gcd(i, math.gcd(j, k))

print(ans)


### FIXED CODE ###

def main():
  import math
  N = int(input())
  gcd={}
  ans=0
  for i in range(1,N+1):
    for j in range(1, N+1):
      key=i*N+j
      gcd[key]=math.gcd(i,j)
  
  for k, i in gcd.items():
    for j in range(1, N+1):
      key=j*N+i
      ans+=gcd[key]
        
  print(ans)
 
if __name__=='__main__':
  main()
### BUGGY CODE ###

n = int(input())
a = input().rstrip().split(" ")
i = 0
j = 0
ans = []

for i in range(int(n)):
    for j in range(int(n)):
        if int(i) + 1 == int(a[j]):
            print(int(j) + 1 , end = " ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0] * n

for i in range(n):
    b[a[i] - 1] = i + 1
    
for i in range(n):
    print(b[i],end=" ")
### BUGGY CODE ###

import sys
n = int(input())
l = list(map(int, (input().split())))

for i in range(n):
    if len([ a for a in l if  l[0] -1 > a]) > 0:
        print('No')
        sys.exit()
    else:
        l = l[1::]
print('Yes')


### FIXED CODE ###

import sys
n = int(input())
l = list(map(int, (input().split())))

max = l[0]
for i in range(n):
    if max - 1 > l[i]:
        print('No')
        sys.exit()
    elif l[i] > max:
        max = l[i]
print('Yes')
### BUGGY CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

k = int(input())
sum = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        for k in range(1, k + 1):
            sum += gcd(gcd(i, j), k)
print(sum)

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

k = int(input())
sum = 0

for i in range(1, k + 1):
    for j in range(1, k + 1):
        gcd_ij = gcd(i, j)
        for k in range(1, k + 1):
            sum += gcd(gcd_ij, k)
print(sum)
### BUGGY CODE ###

N=int(input())
lis=[]
ans=0
for i in range(N):
    s=input()
    if not s in lis:
        ans+=1
        lis.append(s)
print(ans)

### FIXED CODE ###

import collections

N=int(input())
lis=[]
for i in range(N):
    s=input()
    lis.append(s)
c = collections.Counter(lis)
print(len(c))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*n
ac=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        ac+=1
    a[i]=ac
for i in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

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

if N == 1:
    print(1)
    exit()
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > 10**6:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > A[-1]:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and M[h+dh][w+dw] == -1:
                        if (dh, dw) in move:
                            heappush(q, (dist, h+dh, w+dw))
                        else:
                            heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])


    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

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

n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(len(a)-1):
  for j in range(i + 1, len(a)):
    s += a[i]*a[j]
print(s % 1000000007)



### FIXED CODE ###

n = int(input())
s = 0
a = list(map(int, input().split()))
sum_tmp = sum(a[1:len(a)])
for i in range(len(a)-1):
  s += a[i] * sum_tmp
  sum_tmp -= a[i + 1]
print(s % 1000000007)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
a.sort()
# Combination O(k)
MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans

for i in range(len(a)):
    tmp=0
    if i>=k-1:
        tmp=comb(i,k-1)
    vv=0
    if n-i-1>=k-1:
        vv=comb(n-i-1,k-1)
    ans+=a[i]*(tmp-vv)
    ans%=MOD

print(ans%MOD)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
a.sort()
# Combination O(k)
MOD=10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb=Combination(10**5)

for i in range(len(a)):
    tmp=0
    if i>=k-1:
        tmp=comb(i,k-1)
    vv=0
    if n-i-1>=k-1:
        vv=comb(n-i-1,k-1)
    ans+=a[i]*(tmp-vv)
    ans%=MOD

print(ans%MOD)
### BUGGY CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
for i in range(1, N+1):
	s += dp[i]
	for l, r in lr:
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			break
print(ans)



### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

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

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	s %= mod
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)
### BUGGY CODE ###


N = int(input())

D = [int(a) for a in input().split() ]

if D[0] != 0 or D.count(0) !=1:
    print("0")
    exit()

D.sort()
counted = []

for i in range(1,N):
    c = D.count(i)
    if c != 0:
        counted.append(c)

#calc
result = 1
x = counted[0]
for i in range(1,len(counted)):
    y = counted[i]
    result = result * pow(x,y)
    x = y
print(result%998244353)





### FIXED CODE ###

import collections
N = int(input())

D = [int(a) for a in input().split() ]

counted = collections.Counter(D)

if D[0] != 0 or counted[0] !=1:
    print("0")
    exit()

#calc
result = 1
x = counted[1]
for i in range(2,N+1):
    y = counted[i]
    result = result * pow(x,y) %998244353
    x = y
print(result)
### BUGGY CODE ###

N, Q = map(int, input().split())
S=input()
l=list()
r=list()
for i in range(Q):
  L,R=map(int, input().split())
  S2=S[L-1:R].split("AC")
  print(len(S2)-1)

### FIXED CODE ###

N, Q = map(int, input().split())
S=list(input())
Snum=list()
Snum.append(0)
Snum.append(0)
for i in range(1,N):
  if S[i]=="C" and S[i-1]=="A":
    Snum.append(Snum[i]+1)
  else:
    Snum.append(Snum[i])
for i in range(Q):
  L,R=map(int, input().split())
  print(Snum[R]-Snum[L])
### BUGGY CODE ###

import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
sx=[]
sy=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	sx.append(a1)
	y.append(a2)
	sy.append(a2)

#print "# x,y"
#print x
#print y


ans=10**20
#print ans
for i in range(N):
	for j in range(N):
		for k in range(N):
			for l in range(N):
				cnt=0
				if x[i]<x[j] and y[k]<y[l]:
					#print i,j,k,l,x[i],y[k],x[j],y[l],sx.index(x[i]),sx.index(x[j]),abs(x[i]-x[j])*abs(y[k]-y[l])
					for m in range(N):
						x_t=x[m]
						y_t=y[m]
						if (x_t>=x[i] and x_t<=x[j]) or (x_t>=x[j] and x_t<=x[i]):
							if (y_t>=y[k] and y_t<=y[l]) or (y_t>=y[l] and y_t<=y[k]):
								cnt+=1
					
				
				#print cnt
				if cnt>=K:
					#print x[i],y[k],x[j],y[l],cnt,abs(x[i]-x[j])*abs(y[k]-y[l])
					ans=min(ans,abs(x[i]-x[j])*abs(y[k]-y[l]))


print ans


### FIXED CODE ###

import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
pts=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
	pts.append([a1,a2])

#print "# x,y"
x.sort()
y.sort()
#print x
#print y

#print "# pts"
#print pts
pts.sort(key=lambda x:x[0])
#print pts

ans=10**20


for y1 in y:
	for y2 in y:
		if y1>=y2:
			continue
		for x1 in x:
			cnt=0
			for p in pts:
				if p[0]>=x1 and p[1]>=y1 and p[1]<=y2:
					#print p[0],p[1],x1,y1,y2
					cnt+=1
					if cnt==K:
						x2=p[0]
						#print x1,y1,x2,y2,cnt,abs(x2-x1)*abs(y2-y1)
						ans=min(ans,abs(x2-x1)*abs(y2-y1))
						break

print ans
### BUGGY CODE ###

# coding: utf-8
k = int(input())
kx = k
if k % 2 == 1:
    while True:
        num = list(str(kx))
        if all(kx == "7" for kx in num):
            print(len(str(kx)))
            break
        kx = kx + k
else:
    print("-1")


### FIXED CODE ###

# coding: utf-8
k = int(input())
ans = -1
x = 7

for i in range(k):
    if x % k == 0:
        ans = i + 1
        break
    x = (10 * x + 7) % k
print(ans)
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
  
if 1 not in A:
  ans=-1
else:
  ans=0
  for i in range(1,n+1):
    if i in A:
      k=A.index(i)
      ans+=k
      A=A[k+1:]
    else:
      ans+=len(A)
      break
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]

k=1
cnt=0
for i in range(n):
  if A[i]!=k:
    cnt+=1
  else:
    k+=1
if cnt==n:
  print(-1)
else:
  print(cnt)
### BUGGY CODE ###

N = int(input()) 
A = list(int(i) for i in input().split())  
Q = int(input()) 
B_C = [[int(i) for i in input().split()] for i in range(Q)] 
for j in range(Q):
  #print(j)
  A = [B_C[j][1] if i == B_C[j][0] else i for i in A]
  print(sum(A))

### FIXED CODE ###

N = int(input()) 
A = list(int(i) for i in input().split())  
Q = int(input()) 
B_C = [[int(i) for i in input().split()] for i in range(Q)] 
first_sum = sum(A)
import collections
c = collections.Counter(A)
for i in range(Q):
  change_value = (B_C[i][1]-B_C[i][0])*c[B_C[i][0]]
  c[B_C[i][1]] += c[B_C[i][0]]
  c[B_C[i][0]] = 0
  first_sum += change_value
  print(first_sum)
  #print(c)
### BUGGY CODE ###

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

import bisect

for i in range(M):
  x = A[-1]//2
  insert_index = bisect.bisect_left(A[:-1],x)
  A = A[:-1] 
  A.insert(insert_index,x)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(lambda x:(-1)*int(x), input().split()))
import heapq  # heapqライブラリのimport

heapq.heapify(A)  # リストを優先度付きキューへ

# 最小値の取り出し

for i in range(M):
  heapq.heappush(A, ((-1)*heapq.heappop(A))//2*(-1))

print(sum(A)*(-1))
### BUGGY CODE ###

N,M = map(int,input().split())
#低いやつを引いていく感じ
Hlist = list((int(x) for x in input().split()))
delete_list = list()
for i in range(M):
    A,B = map(int, input().split())
    if(Hlist[A-1] == Hlist[B-1]) :
        delete_list.append(A-1)
        delete_list.append(B-1)
    elif(Hlist[A-1] > Hlist[B-1]) :
        delete_list.append(B-1)
    else :
        delete_list.append(A-1)

delete_list = list(set(delete_list))#重複を消す
ans_list = Hlist.copy()
for d in delete_list:
    ans_list.remove(Hlist[d])

print(len(ans_list))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
#低いやつを引いていく感じ
Hlist = list(int(x) for x in input().split())

flag = [1]*N

for i in range(M):
    A,B = map(int, input().split())
    A -= 1
    B -= 1
    if(Hlist[A] == Hlist[B]) :
        flag[A] = 0
        flag[B] = 0
    elif(Hlist[A] > Hlist[B]) :
        flag[B] = 0
    else :
        flag[A] = 0
print(sum(flag))
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for a in range(n):
  if a < n - 2:
    for b in range(a+1, n-1, 1):
      for c in range(b+1, n, 1):
        if li[a] + li[b] <= li[c]:
          break
        if li[a] < li[b] + li[c] and li[b] < li[c] + li[a] and li[c] < li[a] + li[b]:
          ans += 1
            
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for i in range(n):
  for j in range(i+1, n):
    cnt = bisect.bisect_left(li, li[i]+li[j])
    ans += cnt - j - 1
            
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, Y = map(int, input().split())
cnt = 0
for x in range(N+1):
    for y in range(N+1):
        for z in range(N+1):
            if Y == 10000*x+5000*y+1000*z:
                if N == x+y+z:
                    cnt = 1
                    li = [x, y, z]          
if cnt == 1:
    print(li[0], li[1], li[2])
else:
    print(-1, -1, -1)
                

### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import exit
n, y  = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i+5000*j+1000*(n-i-j) == y:
            print(i, j, n-i-j)
            exit()
print(-1, -1, -1)
### BUGGY CODE ###

n,k=map(int,input().split())
num=0
for i in range(k,n+2):
    minsum=maxsum=0
    for j in range(i):
        minsum+=j
        maxsum+=n-j
    num+=maxsum-minsum+1
print(num)

### FIXED CODE ###

n,k=map(int,input().split())
num=0
for i in range(k,n+2):
    num+=i*(n-i+1)+1
print(num%(10**9+7))
### BUGGY CODE ###

import sys
import numpy as np

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def matrix_cal(A, B, mod):
    a, b = A.shape
    c, d = B.shape
    # print(a, b, c, d)
    assert(b == c)
    ans = np.zeros((a, d), dtype=np.int64)
    for aa in range(a):
        for dd in range(d):
            v = 0
            for bb in range(b):
                v = (v + A[aa][bb] * B[bb][dd]) % mod
            ans[aa][dd] = v
    return ans


def matrix_pow(A, n, mod=0):
    if n == 1:
        return A
    a = matrix_pow(A, n//2, mod)
    ans = matrix_cal(a, a, mod)
    if n % 2 == 1:
        ans = matrix_cal(ans, A, mod)
    ans %= mod
    return ans


N, K = na()
A = np.array(naa(N), dtype=np.int64)
mod = 10 ** 9 + 7

B = matrix_pow(A, K, mod)

ans = 0
for i in range(N):
    for j in range(N):
        ans = (ans + B[i][j]) % mod


print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def matrix_cal(A, B, mod):
    a = len(A)
    b = len(A[0])
    c = len(B)
    d = len(B[0])

    assert(b == c)
    ans = [[0] * d for _ in range(a)]
    for aa in range(a):
        for dd in range(d):
            v = 0
            for bb in range(b):
                v = (v + A[aa][bb] * B[bb][dd]) % mod
            ans[aa][dd] = v
    return ans


def matrix_pow(A, n, mod=0):
    if n == 1:
        return A
    a = matrix_pow(A, n//2, mod)
    ans = matrix_cal(a, a, mod)
    if n % 2 == 1:
        ans = matrix_cal(ans, A, mod)
    return ans


N, K = na()
A = naa(N)
mod = 10 ** 9 + 7

B = matrix_pow(A, K, mod)

ans = 0
for i in range(N):
    for j in range(N):
        ans = (ans + B[i][j]) % mod


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

n=int(input())
a=list(map(int, input().split()))
count=[0]*(n+1)
output=[0]*(n+1)
for i in range (n):
    count[a[i]]+=1
#print(count)
for i in range(n):
    count[a[i]]-=1
    #print(count)
    c=0
    for j in range(1,n+1):
        c=c+count[j]*(count[j]-1)//2
    output[i]=c
    count[a[i]] +=1

for i in range (n):
    print(output[i])

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
count=[0]*(n+1)
for i in range (n):
    count[a[i]]+=1
m=0
for i in range (1,n+1):
    m+=count[i]*(count[i]-1)//2
for i in range (n):
   print(m-(count[a[i]]-1))
### BUGGY CODE ###

s = input()
max_ = 0
pre = s[0]
ren = 1
for i in range(1, len(s)):
    if s[i] == pre:
        ren += 1
        max_ = max(max_, ren)
    else:
        ren = 1
        pre = s[i]
from collections import deque
status = deque([[1] * len(s)])
for i in range(max_):
    sta = [0] * len(s)
    if s[1] == 'L':
        sta[0] = status[i][1]
    else:
        sta[0] = 0
    if s[-2] == 'R':
        sta[-1] = status[i][-2]
    else:
        sta[-1] = 0
    a = [[1] * len(s)]
    for j in range(1, len(s) - 1):
        #print(sta)
        if s[j - 1] == 'R':
            sta[j] += status[i][j - 1]
        if s[j + 1] == 'L':
            sta[j] += status[i][j + 1]
    status.append(sta)
#for i in range(1 + max_ - 2):
    #status.popleft()
if (max_ - 2) % 2 == 0:
    print(' '.join([str(i) for i in status[-1]]))
else:
    print(' '.join([str(i) for i in status[-2]]))

### FIXED CODE ###

li = input()
n = len(li)
child_li = [0] * n

ruiseki = 0
for i in range(n - 1):
    if li[i] == 'R':
        ruiseki += 1
        if li[i + 1] == 'L':
            child_li[i + 1] = ruiseki // 2
            child_li[i] = (ruiseki + 1) // 2
    else:
        ruiseki = 0
        
ruiseki = 0
for i in range(n - 1, 0, -1):
    if li[i] == 'L':
        ruiseki += 1
        if li[i - 1] == 'R':
            child_li[i - 1] += ruiseki // 2
            child_li[i] += (ruiseki + 1) // 2
    else:
        ruiseki = 0
print(*child_li)
### BUGGY CODE ###

def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bit = 0
  for i in range(N):
    bit += int(X[i])*pow(2,N-1-i)
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bit - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bit + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')

### FIXED CODE ###

def solve():
  N = int(input())
  X = input()
  x = sum(map(int,list(X)))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = dp[i%sum(map(int,list(bin(i)[2:])))]+1
  cnt1 = 0
  if x>1:
    for i in range(N):
      cnt1 += int(X[-i-1])*pow(2,i,x-1)
      cnt1 %= x-1
  cnt2 = 0
  for i in range(N):
    cnt2 += int(X[-i-1])*pow(2,i,x+1)
    cnt2 %= x+1
  
  ans = [0]*N
  for i in range(N):
    if X[i]=='1':
      if x==1:
        ans[i] = 0
      else:
        num = (cnt1-pow(2,N-i-1,x-1))%(x-1)
        ans[i] = dp[num]+1
    else:
      num = (cnt2+pow(2,N-i-1,x+1))%(x+1)
      ans[i] = dp[num]+1
  return ans
print(*solve(),sep='\n')