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

N= int(input())
A = list(map(int, input().split()))
B=[0]*N
C=[0]*N
for i in range(N):
    B[i]=A.count(i+1)
for i in range(N):
    B[i] = B[i] - 1
    for j in range(N):
        if B[j] > 1:
            C[i] = C[i] + B[j] * (B[j] - 1) / 2
    B[i] = B[i] + 1

for i in range(N):
    print(int(C[A[i]-1]))


### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))
### BUGGY CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    for b in range(len(B)):
        if (a+1)*(b+1) > K:
            continue
        for c in range(len(C)):
            if (a+1)*(b+1)*(c+1) > K:
                continue
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

k, s = map(int, input().split())

li = [1 for x in range(0, k + 1) for y in range(0, k + 1) for z in range(0, k + 1) if x + y + z == s]
print(len(li))


### FIXED CODE ###

k, s = map(int, input().split())
r = range(0, k + 1)
cnt = 0
for x in r:
    for y in r:
        if s - k <= x + y <= s:
            cnt += 1
print(cnt)
### BUGGY CODE ###

n,k= list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
b=[1]*n
for j in range(0,k):
        b[k-1]*=a[j]
for i in range(k+1,n+1):
    b[i-1]*=b[i-2]*a[i-1]//a[i-k-1]

    

for i in range(k,n):
    if b[i-1]<b[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

    
for i in range(k+1,n+1):
    b[i-1]=a[i-1]/a[i-k-1]

    

for i in range(k,n):
    if 1<b[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N = input()
c = 0
p = [0 for i in range(N)]
for i in range(0,N):
	p[i] = input()
for i in range(N):
	j = p[i]-1
	while(j > 1):
		if(p[i]%j == 0):break
		j -= 1
	if(j == 1):
		c += 1
print c

### FIXED CODE ###

import math
N = input()
c = 0
p = [0 for i in range(N)]
for i in range(0,N):
	p[i] = input()
for i in range(N):
	s = math.sqrt(p[i])
	j = 2
	while(j <= s):
		if(p[i]%j == 0):
			break
		j += 1
	if(j > s):
		c += 1
print c
### BUGGY CODE ###

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

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(301):
    for j in range(301):
        for i in range(301):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])

### FIXED CODE ###

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

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(lst[2]+1):
    for j in range(lst[1]+lst[2]+1-k):
        for i in range(lst[0]+lst[1]+lst[2]+1-k-j):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    query = list(input().split())
    if query[0] == "1":
        S = S[::-1]
    else:
        if query[1] == "1":
            S = query[2]+S
        else:
            S = S+query[2]
print(S)

### FIXED CODE ###

s = input()
q = int(input())
list1 = []
list2 = []
flag = 1
for i in range(q):
    in_line = input().split()
    if in_line[0] == "1":
        flag *= -1
    else:
        if in_line[1] == "1":
            if flag == 1:
                list1.append(in_line[2])
            else:
                list2.append(in_line[2])
        else:
            if flag == 1:
                list2.append(in_line[2])
            else:
                list1.append(in_line[2])
if flag == 1:
    print("".join(list1[::-1]) + s + "".join(list2))
else:
    print("".join(list2[::-1]) + s[::-1] + "".join(list1))
### BUGGY CODE ###

num = int(input())

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

ans = 0

for i in range(0,num-1):
    for j in range(i+1,num):
        c = arr[i] ^ arr[j]
       
        ans += (c % 1000000007)
        

print(ans% 1000000007)

### FIXED CODE ###


def sumXOR(arr,n): 
      
    sum = 0
    for i in range(0, 65): 
    
        #  Count of zeros and ones 
        zc = 0
        oc = 0
           
        # Individual sum at each bit position 
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1
                  
            else: 
                oc = oc + 1
            arr[j] = arr[j] // 2
          
           
        # calculating individual bit sum  
        idsum = oc * zc * (1 << i) 
    
        # final sum     
        sum = sum + idsum;  
      
    return sum%(1000000007)
  
  
  
# driver function  
sum = 0
n = int(input())
arr = list(map(int,input().split()))
arr.sort()
sum = sumXOR(arr, n); 
print (sum)
### BUGGY CODE ###

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

def main():
    for i in range(len(a_n)):
        for j in range(i):
            if a_n[i] == a_n[j]:
                print('NO')
                return 0
    print('YES')
    return 0

main()

### FIXED CODE ###

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

def has_duplicates(seq):
    return len(seq) != len(set(seq))

if has_duplicates(a_n):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

import itertools
from sys import stdin
N=int(input())
st=list(stdin.readline().strip())
count=0
cnt=0
stt=set(st)
stt=list(stt)
num=["0","1","2","3","4","5","6","7","8","9"]
num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    for i in range(N):
        if cnt==0 and number[0]==st[i]:
            cnt+=1
        elif cnt==1 and number[1]==st[i]:
            cnt+=1
        elif cnt==2 and number[2]==st[i]:
            cnt+=1
            break
    if cnt==3:
        count+=1
    cnt=0
print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = False

    for a in A:
        if a>0:
            plus = True
            break

    A.sort(reverse=True)

    if K%2==1 and plus==False:
        ans = 1
        for i in A[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A = deque(A)
        ans = 1
        if K%2==1:
            ans *= A.popleft()
        for _ in range(K//2):
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans *= A.popleft()*A.popleft()%MOD
            else:
                ans *= A.pop() * A.pop() % MOD
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = map(int, readline().split())
    A = list(map(int, readline().split()))
    MOD = int(1e9) + 7
    A.sort()
    ans = 1
    if A[n - 1] == 0 and (k & 1):
        ans = 0
    elif A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            ans = (ans * A[i]) % MOD
    else:
        i = 0
        j = n - 1
        if k & 1:
            ans = (ans * A[j]) % MOD
            j -= 1
            k -= 1
        k >>= 1
        for itr in range(k):
            left_product = A[i] * A[i + 1]
            right_product = A[j] * A[j - 1]
            if left_product > right_product:
                ans = (ans * left_product) % MOD
                i += 2
            else:
                ans = (ans * right_product) % MOD
                j -= 2

    print(ans % MOD)

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

n, m = (int(_) for _ in input().split())
e = [[int(i) for i in input().split()] for i in range(m)]

for pi,pj in e:
    t = [yj for pj,yj in e if(pj == pi)]
    t.sort()
    print('{0:06d}'.format(pi)+'{0:06d}'.format(t.index(pj)+1))

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

def solve(N: int, M: int, P: "List[int]", Y: "List[int]"):
    # もとの値
    val = [[] for i in range(N+1)]
    for pi, yi in [[P[i], Y[i]] for i in range(M)]:
        val[pi].append(yi)

    for i in val:
        i.sort()


    a = sorted([[P[i], Y[i]] for i in range(M)], key=lambda x:(x[0],x[1]))

    for p, y in [[P[i], Y[i]] for i in range(M)]:
        c_id = bisect.bisect_left(val[p], y)
        print(str(p).zfill(6)+str(c_id+1).zfill(6))
    
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    M = int(next(tokens))  # type: int
    P = [int()] * (M)  # type: "List[int]" 
    Y = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        P[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, M, P, Y)

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

N, Q = map(int, input().split())
s = input()
AClist = []

for i in range(N - 1):
  if(s[i:i + 2] == "AC"): AClist.append(i)

for i in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  result = 0
  idx = 0
  
  while(idx < len(AClist) and l > AClist[idx]):
    idx += 1
    
  while(idx < len(AClist) and AClist[idx] + 1 <= r):
    idx += 1
    result += 1
  
  print(result)

### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
AClist = [0] * N

for i in range(N - 1):
  AClist[i + 1] = AClist[i] + int(s[i:i + 2] == "AC")
  
for i in range(Q):
  l, r = map(int, input().split())
  print(AClist[r - 1] - AClist[l - 1])
### BUGGY CODE ###

N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)
    
    

### FIXED CODE ###

N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  val=len(set)+1
  if not(val in set):
    return(val)
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)

# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         left = mid1
#     else:
#         right = mid2
ans = 0
for i in range(1, N+1):
    ans = max(ans, f(i))
print(ans)

    

### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         if left == mid1:
#             break
#         left = mid1
#     else:
#         if right == mid1:
#             break
#         right = mid2

# ans = f(left)
# for i in range(left, right+1):
#     ans = max(ans, f(i))
# print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"

ans = 0
if B > N:
    ans = f(N)
else:
    ans = f(B-1)

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

S = list(input())
count = 0
flag = 0
j = 0
while 1:
    for i in range(len(S)-1):
        if S[i] != S[i+1]:
            S.pop(i)
            S.pop(i)
            count += 2
            break
        if i==len(S)-2:
            flag = 1
    if len(S)==0 or  len(S) == 1 or flag == 1:
        break
print(count)

### FIXED CODE ###

S = list(input())
count_0 = 0
count_1 = 0


for i in S:
    if i == "0":
        count_0 += 1
    if i == "1":
        count_1 += 1

print(min(count_0, count_1)*2)
### BUGGY CODE ###

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

def penalty(day, last, c):
    val = 0
    for i in range(26):
        val += c[i] * (day - last[i])
    return val

def update(day, t, q, score, c, last):
    t[day] = q
    for i in range(day, len(score)):
        for j in range(26):
            last[i][j] = last[i-1][j]
        score[i] = score[i-1] + s[i][t[i]]
        last[i][t[i]] = i
        score[i] -= penalty(i, last[i], c)

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(input()) - 1
M = int(input())

last = [[0]*26 for _ in range(D+1)]
score = [0]*(D+1)

for i in range(1, D+1):
    for j in range(26):
        last[i][j] = last[i-1][j]
    score[i] = score[i-1] + s[i][t[i]]
    last[i][t[i]] = i
    score[i] -= penalty(i, last[i], c)

ans = [None]*M
for i in range(M):
    d, q = map(int, input().split())
    update(d, t, q-1, score, c, last)
    ans[i] = score[-1]

for v in ans:
    print(v)

### FIXED CODE ###

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

def calcScore(t, s, c):
    scores = [0]*26
    lasts = [0]*26
    for i in range(1, len(t)):
        scores[t[i]] += s[i][t[i]]
        dif = i - lasts[t[i]]
        scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
        lasts[t[i]] = i
    for i in range(26):
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2
    return scores

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(input()) - 1
M = int(input())

scores = calcScore(t, s, c)

ans = [None]*M
for i in range(M):
    d, q = map(int, input().split())
    t[d] = q-1
    ans[i] = sum(calcScore(t, s, c))

for v in ans:
    print(v)
### BUGGY CODE ###

def count(num_lst):
    count = [0]*60
    for num in num_lst:
        for i in range(60):
            tmp = 0
            if tmp == num:
                break
            if num & (1<<i):
                count[i] += 1
                tmp += 2**i
    return count

n = int(input())
num_list = list(map(int,input().split()))
mod = 10**9 + 7

count = count(num_list)
ans = 0
for i in range(60):
    if i == 0:
        pow_two = 1
    else:
        pow_two = pow_two * 2 % mod
    ans += pow_two * count[i] * (n - count[i]) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())
num_list = np.array(input().split(), dtype = np.int64)
mod = 10**9 + 7

ans = 0
for i in range(60):
    b = np.count_nonzero(num_list >> i & 1)
    if i==0:
        pow_two = 1
    else:
        pow_two = pow_two * 2 % mod
    ans += pow_two * b * (n-b) % mod
    ans %= mod
    
print(ans)
### BUGGY CODE ###

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

#n = int(input())
#a,b = map(int,input().split())
a_L = list(map(int,input().split()))
ans = 1
for i in range(n):
    ans = ans*a_L[i]
if ans > 10**18:
    print(-1)
    exit()

print(ans)

### FIXED CODE ###

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

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

a_L = list(sorted(a_L))
if a_L[0] == 0:
    print(0)
    exit()

ans = 1
for i in range(n):
    ans = ans*a_L[i]
    if ans > 10**18:
        print(-1)
        exit()

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

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n = int(input()) #n:頂点数　w:辺の数
w=n-1
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y,z = map(int,input().split())
    x=x-1
    y=y-1
    cost[x][y] = z
    cost[y][x] = z
A=dijkstra(0,n,w,cost)
for i in range(n):
  print(A[i]%2)

### FIXED CODE ###

from collections import deque
n=int(input())
A=[[[] for j in range(2)] for i in range(n)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  w=w%2
  A[u-1][0].append(v-1)
  A[u-1][1].append(w)
  A[v-1][0].append(u-1)
  A[v-1][1].append(w)
B=deque([0])
C=[0]*n
C[0]=1
ans=[0]*n
while len(B)>0:
  s=B[0]
  B.popleft()
  for i in range(len(A[s][0])):
    if C[A[s][0][i]]==0:
      B.append(A[s][0][i])
      C[A[s][0][i]]=1
      ans[A[s][0][i]]=(ans[s]+A[s][1][i])%2
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
miss=0
if N%2==0:
    for i in range(int(N/2)):
        if A.count((2*i+1))!=2:
            miss=1
    if miss==1:
        print(0)
    else:
        print(int((2**int(N/2))%(10e9+7)))
if N%2==1:
    if not 0 in A:
        miss=1
    for i in range(int((N-1)/2)):
        if A.count((2*i+2))!=2:
            miss=1
    if miss==1:
        print(0)
    else:
        print(int((2**int((N-1)/2))%(10e9+7)))


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
A.sort()
miss=0

if N%2==0:
    for i in range(int(N/2)):    
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+1:
                A.pop(0)
            else:
                miss=1
                break
                
    if miss==1:
        print(0)
    else:
        print(int((2**int(N/2))%(10**9+7)))

else:
    if A[0]!=0:
        miss=1
        A.pop(0)
    else:
        A.pop(0)
    for i in range(int((N-1)/2)):
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+2:
                A.pop(0)
            else:
                miss=1
                break
                
    if miss==1:
        print(0)
    else:
        print(int((2**int((N-1)/2))%(10**9+7)))
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
ans = 0
sushi = defaultdict(list)

for _ in range(n):
    t, d = map(int, input().split())
    sushi[t].append(d)

most_tasty = []
other_sushi = []

for key, value in sushi.items():
    value.sort(reverse=True)
    most_tasty.append(value[0])
    value.pop(0)
    other_sushi += value

most_tasty.sort(reverse=True)
other_sushi.sort(reverse=True)
for i in range(1, k + 1):
    if i > len(most_tasty):
        break
    num = min(i, len(most_tasty))
    point = sum(most_tasty[:i])
    point += sum(other_sushi[:(k - i)])
    point += i ** 2
    ans = max(ans, point)

print(ans)


### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
top = [0] * n
sub = []

for i in range(n):
    t, d = map(int, input().split())
    t -= 1
    if top[t] == 0:
        top[t] = d
    else:
        if d > top[t]:
            sub.append(top[t])
            top[t] = d
        else:
            sub.append(d)

top.sort(reverse=True)
top_sum = [0]
sub.sort(reverse=True)
sub_sum = [0]

for p in top:
    if p == 0:
        top_sum.append(-1)
    else:
        top_sum.append(top_sum[-1] + p)

for p in sub:
    sub_sum.append(sub_sum[-1] + p)

ans = 0

for i in range(1, k + 1):
    if (len(sub_sum) - 1) >= (k - i) and top_sum[i] != -1:
        ans = max(ans, top_sum[i] + sub_sum[k - i] + i ** 2)

print(ans)