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

## coding: UTF-8
#最後の方のテストケースでREになってしまう。時間切れ。
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product

N = int(input())

s = input().split()
p = [int(w) for w in s]
#print('p:{}'.format(p))

number_list = [0 for i in range(N)]
'''
for i in range(N):
    counter = 0
    for j in range(N):
        if(p[j] == i+1):
            counter +=1
    number_list.append(counter)
'''
#print(number_list)

for i in range(N):
    number_list[p[i] - 1] += 1
#print(number_list)



def n_C_2(n):
    if(n == -1):
        return 0
    else:
        return int(n * (n-1) / 2)


full_combi = []
pickup_combi = []
print_combi = []

for i in range(N):
    full_combi.append(n_C_2(number_list[i]))
    pickup_combi.append(n_C_2(number_list[i] - 1))
#print('full_combi:{}'.format(full_combi))
#print('pickup_combi:{}'.format(pickup_combi))

for i in range(N):
    print_combi.append(sum(full_combi) - full_combi[i] + pickup_combi[i])
#print('print_combi:{}'.format(print_combi))

for i in range(N):
    index = p[i] - 1
    print(print_combi[index])

### FIXED CODE ###

## coding: UTF-8
#最後の方のテストケースでREになってしまう。時間切れ。
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product

N = int(input())

s = input().split()
p = [int(w) for w in s]
#print('p:{}'.format(p))

number_list = [0 for i in range(N)]
'''
for i in range(N):
    counter = 0
    for j in range(N):
        if(p[j] == i+1):
            counter +=1
    number_list.append(counter)
'''
#print(number_list)

for i in range(N):
    number_list[p[i] - 1] += 1
#print(number_list)



def n_C_2(n):
    if(n == -1):
        return 0
    else:
        return int(n * (n-1) / 2)


full_combi = []
pickup_combi = []
print_combi = []

for i in range(N):
    full_combi.append(n_C_2(number_list[i]))
    pickup_combi.append(n_C_2(number_list[i] - 1))
#print('full_combi:{}'.format(full_combi))
#print('pickup_combi:{}'.format(pickup_combi))

all_full = sum(full_combi)
for i in range(N):
    print_combi.append(all_full - full_combi[i] + pickup_combi[i])
#print('print_combi:{}'.format(print_combi))

for i in range(N):
    index = p[i] - 1
    print(print_combi[index])
### BUGGY CODE ###

N = input()
a = []
for i in range(int(N)):
  x = input()
  
  if str(x in a) != "True":
    a.append(x)
print(len(a))

### FIXED CODE ###

N = input()
n = int(N)
a = {input() for i in range(n)}  
print(len(a))
### BUGGY CODE ###

X, Y, Z, K=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
A=[-A[i] for i in range(X)]
B=[-B[i] for i in range(Y)]
C=[-C[i] for i in range(Z)]
A.sort()
B.sort()
C.sort()

import heapq
nums=[[A[0]+B[0]+C[0], 0, 0, 0]]
heapq.heapify(nums)

sumi=[[[0]*Z for __ in range(Y)] for _ in range(X)]
sumi[0][0][0]=1
for _ in range(K):
  out, a, b, c=heapq.heappop(nums)
  print(-out)
  if a<X-1 and sumi[a+1][b][c]==0:
    heapq.heappush(nums, [A[a+1]+B[b]+C[c], a+1, b, c])
    sumi[a+1][b][c]=1
  if b<Y-1 and sumi[a][b+1][c]==0:
    heapq.heappush(nums, [A[a]+B[b+1]+C[c], a, b+1, c])
    sumi[a][b+1][c]=1
  if c<Z-1 and sumi[a][b][c+1]==0:
    heapq.heappush(nums, [A[a]+B[b]+C[c+1], a, b, c+1])
    sumi[a][b][c+1]=1


### FIXED CODE ###

X, Y, Z, K=map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

import heapq
nums=[[-(A[0]+B[0]+C[0]), 0, 0, 0]]
heapq.heapify(nums)

sumi=[[0, 0, 0]]
for _ in range(K):
  out, a, b, c=heapq.heappop(nums)
  print(-out)
  if a<X-1 and not([a+1, b, c] in sumi):
    heapq.heappush(nums, [-(A[a+1]+B[b]+C[c]), a+1, b, c])
    sumi.append([a+1, b, c])
  if b<Y-1 and not([a, b+1, c] in sumi):
    heapq.heappush(nums, [-(A[a]+B[b+1]+C[c]), a, b+1, c])
    sumi.append([a, b+1, c])
  if c<Z-1 and not([a, b, c+1] in sumi):
    heapq.heappush(nums, [-(A[a]+B[b]+C[c+1]), a, b, c+1])
    sumi.append([a, b, c+1])
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] <= d + 1: continue
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
    C = [input().rstrip() for _ in range(H)]
    main(H, W, K, x1, y1, x2, y2, C)
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
sum = 0
for i in range(0,N):
  L_1st= L[i]
  for j in range(i+1,N):
    L_2nd = L[j]
    c_min = L_2nd-L_1st+1
    c_max = L_2nd+L_1st-1
    l = bisect.bisect_left(L,c_min,lo = j+1)
    if l!= N:
      r = bisect.bisect_right(L,c_max,lo = j+1)
      if r:
        r = r-1
        if r>= l:
          sum += r-l+1
print(sum)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
sum = 0
for i in range(0,N):
  L_1st= L[i]
  for j in range(i+1,N):
    L_2nd = L[j]
    c_min = L_2nd-L_1st+1
    c_max = L_2nd+L_1st-1
    l = bisect.bisect_left(L,c_min,lo = j+1)
    if l!= N:
      r = bisect.bisect_right(L,c_max,lo = j+1)
      if r:
        r = r-1
        if r>= l:
          sum += r-l+1
print(sum)
### BUGGY CODE ###

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

# solve
ans = []

# check if _b can be constructed.
# returns True/False
def dfs(_b, _ans):
	
	for i in range(0, len(_b)):
		
		if i + 1 == _b[i]:
			_b2 = _b[:]
			_ans2 = _ans[:]
			_ans2.append(_b2[i])
			_b2.pop(i)
			
			if dfs(_b2, _ans2) == True:
				return True
	
	if len(_b) == 0:
		## print answer
		_ans.reverse()
		for i in _ans:
			print(i)
		return True
		
	else:
		return False


if not dfs(b,[]):
	print(-1)

### FIXED CODE ###

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

# solve
ans = []

# necessary condition
def cond(_b):
	hist = [0]*(len(_b)+1)
	
	for i in range(0, len(_b)):
		if _b[i] > i + 1:
			return False
	
	return True

# check if _b can be constructed.
# returns True/False
def dfs(_b, _ans):
	
	if not cond(_b):
		return False
	
	for i in range(0, len(_b)):
		
		if i + 1 == _b[i]:
			_b2 = _b[:]
			_ans2 = _ans[:]
			_ans2.append(_b2[i])
			_b2.pop(i)
			
			if dfs(_b2, _ans2) == True:
				return True
	
	if len(_b) == 0:
		## print answer
		_ans.reverse()
		for i in _ans:
			print(i)
		return True
		
	else:
		return False


if not dfs(b,[]):
	print(-1)
### BUGGY CODE ###

s=raw_input().strip()
t=raw_input().strip()
n=len(s)
m=len(t)
z=[[0]*(m+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(m):
        if s[i]==t[j]:
            z[i+1][j+1]=z[i][j]+1
        else:
            z[i+1][j+1]=max(z[i+1][j],z[i][j+1])
i=n-1
j=m-1
a=[]
while i>=0 and j>=0:
    if s[i]==t[j]:
        a.append(s[i])
        i-=1
        j-=1
    elif z[i][j+1]>z[i+1][j]:
        i-=1
    else:
        j-=1
print ''.join(a[::-1])

### FIXED CODE ###

s=raw_input().strip()
t=raw_input().strip()
n=len(s)
m=len(t)
z=[[0]*(m+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(m):
        if s[i]==t[j]:
            z[i+1][j+1]=z[i][j]+1
        else:
            z[i+1][j+1]=max(z[i+1][j],z[i][j+1])
i=n-1
j=m-1
a=[]
while i>=0 and j>=0:
    if s[i]==t[j]:
        a.append(s[i])
        i-=1
        j-=1
    elif z[i][j+1]>z[i+1][j]:
        i-=1
    else:
        j-=1
print ''.join(a[::-1])
### BUGGY CODE ###

N, M = list(map(int, input().split()))
ID = list(range(1, N+1))
for i in range(M):
    L, R = list(map(int, input().split()))
    r = list(range(L, R+1))
    ID = set(ID) & set(r)
    if len(ID) == 0:
        print(0)
        exit()
if len(ID) > N:
    print(N)
else:
    print(len(ID))

### FIXED CODE ###

N, M = list(map(int, input().split()))
LR = [list(map(int,input().split())) for i in range(M)]
max = 1
min = 100000
for i in range(M):
    if max < LR[i][0]:
        max = LR[i][0]
    if min > LR[i][1]:
        min = LR[i][1]
if max <= min:
    print(min - max + 1)
else:
    print(0)
### BUGGY CODE ###

import math
def insert(list, n): 
	j=0
	for j in range(len(list)): 
		if list[j] > n: 
			break
      
	list = list[:j] + [n] + list[j:] 
	return list
n,m=[int(x) for x in input().split()]
s,v=0,[]
for x in input().split():
	x=int(x)
	s+=x
	v.append(x)
v.sort()
while (m>0):
	if (v[-1]==0):
		break
	k=v[-1]/2
	s-=math.ceil(k)
	del v[-1]
	v=insert(v,math.floor(k))
	m-=1
print(s)

### FIXED CODE ###

#coding:utf-8
 
import heapq
 
N, M = map(int, input().split())
invA = []
for a in map(int, input().split()):
    heapq.heappush(invA, -1*a)
for m in range(M):
    heapq.heappush(invA, heapq.heappop(invA)/2)
total = -1*sum(map(int, invA))
 
print(total)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(lambda x:int(x)-1,input().split()))
key=[[] for _ in range(n)]
for i in range(m):
    for j in c[i]:
        key[j].append(i)

ans=float('inf')
def serch(keyset,i):
    global ans
    if i==n:
        s=set([])
        for k in keyset:
            s|=set(c[k])
        if s==set(range(n)):
            ans=min(ans,sum(a[k] for k in keyset))
    else:
        if any(k in key[i] for k in keyset):
            serch(keyset,i+1)
        else:
            for k in key[i]:
                serch(keyset|{k},i+1)

serch(set([]),0)
print(-1 if ans==float('inf') else ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))

dp=[-1]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            if dp[j]<0:
                dp[j]=a[i]
            else:
                dp[j]=min(dp[j],a[i])
for i in range(m):
    for j in range(2**n):
        if dp[j]<0:
            continue
        if dp[c[i]|j]<0:
            dp[c[i]|j]=dp[j]+a[i]
        else:
            dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(dp[-1])
### BUGGY CODE ###

# https://agc024.contest.atcoder.jp/tasks/agc024_a


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

for i in range(K):
    A, B, C = B + C, A + C, A + B

ans = A - B

if ans > 10 ** 18:
    print('Unfair')
else:
    print(ans)

### FIXED CODE ###

# https://agc024.contest.atcoder.jp/tasks/agc024_a


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

if K < 2:
    for i in range(K):
        A, B, C = B + C, A + C, A + B
    ans = A - B

    if ans > 10 ** 18:
        print('Unfair')
    else:
        print(ans)
else:
    if K % 2 == 0:
        ans = A - B
    else:
        ans = -A + B

    if ans > 10 ** 18:
        print('Unfair')
    else:
        print(ans)
### BUGGY CODE ###

s = input()[::-1]
m = 2019
ans = 0
x = 1
tot = 0
cnt = [0] * m
for s in s:
    cnt[tot] += 1
    tot += int(s) * x % m
    tot %= m
    ans += cnt[tot % m]
    x *= 10 % m
print(ans)


### FIXED CODE ###

s = input()[::-1]
m = 2019
ans = 0
x = 1
tot = 0
cnt = [0] * m
cnt[0] = 1
for s in s:
    tot += int(s) * x
    tot %= m
    #ans += cnt[tot]
    x *= 10
    x %= m
    cnt[tot] += 1

print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

from collections import Counter

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

ans = 0
c = Counter(a)
for i in range(min(a), max(a) + 1):
    temp = [value if abs(i - key) <= 1 else 0 for key, value in c.most_common()]
    ans = max(ans, sum(temp))

print(ans)


### FIXED CODE ###

from collections import Counter

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

x = []
for i in a:
    x.append(i)
    x.append(i + 1)
    x.append(i - 1)

ans = max(Counter(x).values())
print(ans)
### BUGGY CODE ###

n = int(input())
a = [i + 1 for i in range(n)]
p = a[1:] + [a[0]]
print(sum([a[i] % p[i] for i in range(n)]))

### FIXED CODE ###

n = int(input())
print(n * (n - 1) // 2)
### BUGGY CODE ###

N,A,B,K = map(int,input().split())
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

P = 2500
pascal = [None] * (P+1)
pascal[0] = [1,0]
for n in range(1,P+1):
    pascal[n] = [1]
    for r in range(1,n+1):
        pascal[n].append(pascal[n-1][r-1] + pascal[n-1][r])
    pascal[n].append(0)

def ncr(n,r):
    if n <= P:
        return pascal[n][r]
    else:
        return mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)
### BUGGY CODE ###

def main():
    s = input()
    s = s[::-1]
    s_len = len(s)
    mod = 2019
    d = [0] * mod
    d[0] = 1
    rev_num = 0
    # 2以上なら共通するmodがあったということになる
    for i in range(s_len):
        rev_num += int(s[i]) * (10**i%mod)
        rev_num %= mod
        d[rev_num] += 1
    # 2以上同じmodがあったらそこから2つ選ぶ選び方
    # それを全てのmodで
    print(sum(i*(i-1)//2 for i in d))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = input()
    s_len = len(s)
    mod = 2019
    d = [0] * mod
    d[0] = 1
    rev_num = 0
    t = 1
    # 2以上なら共通するmodがあったということになる
    for i in reversed(s):
        rev_num += int(i) * t
        rev_num %= mod
        d[rev_num] += 1
        t *= 10
        t %= mod
    # 2以上同じmodがあったらそこから2つ選ぶ選び方
    # それを全てのmodで
    print(sum(i*(i-1)//2 for i in d))
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# EDP F-LCS
import sys
input = sys.stdin.readline


def main():
    s = input()
    t = input()

    dp = [[[0, ""] for j in range(len(t)+1)] for i in range(len(s)+1)]

    for i in range(0, len(s)):
        for j in range(0, len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = [dp[i][j][0]+1, dp[i][j][1]+s[i]]
            else:
                if dp[i+1][j][0] >= dp[i][j+1][0]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

    print(dp[len(s)][len(t)][1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# EDP F-LCS
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""


def main():
    S = input()
    T = input()
    LS = len(S)
    LT = len(T)
    dp = [[0 for j in range(LT+1)] for i in range(LS+1)]

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                if dp[i+1][j] >= dp[i][j+1]:
                    dp[i+1][j+1] = dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i][j+1]

    def rec(i, j):
        if i == 0 or j == 0:
            return

        if S[i-1] == T[j-1]:
            global ans
            ans += S[i-1]
            rec(i-1, j-1)
        elif dp[i-1][j] > dp[i][j-1]:
            rec(i-1, j)
        else:
            rec(i, j-1)

    rec(LS, LT)
    print(ans[::-1])


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

x = -1
y = -1
S = list(input())
for i in range(0, len(S)-1):
    for j in range(i+2, len(S)+1):
        s = S[i:j]
        s_set = list(set(s))
        for s_i in s_set:
            if s.count(s_i) > (len(s)//2):
                s_list = [ii for ii, x in enumerate(s) if x == s_i]
                x = s_list[0]+1+i
                y = s_list[-1]+1+i
                break
print(x, y)

### FIXED CODE ###

# 回答を見て

x = -1
y = -1
S = list(input())

for i in range(len(S)-1):
    if S[i] == S[i+1]:
        x = i+1
        y = x+1
        break
    elif i+2<=len(S)-1:
        if S[i] == S[i+2]:
            x = i+1
            y = x+2
            break
        else:
            pass
    else:
        pass
print(x, y)
### BUGGY CODE ###

import sys

stdin = sys.stdin

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

n = ni()
a = na()
ans = 0
while True:
    dtwo = 0
    for i in range(n):
        if a[i] % 2 == 0 and dtwo == 0:
            a[i]//=2
            dtwo = 1
        else:
            a[i]*=3
    if dtwo == 0:
        break
    ans += 1
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

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

n = ni()
a = na()
# ans = 0
# while True:
#     dtwo = 0
#     for i in range(n):
#         if a[i] % 2 == 0 and dtwo == 0:
#             a[i]//=2
#             dtwo = 1
#         else:
#             a[i]*=3
#     if dtwo == 0:
#         break
#     ans += 1
# print(ans)
ans = 0
for i in range(n):
    tmp = a[i]
    while True:
        if tmp%2 == 0:
            ans += 1
        else:
            break
        tmp = tmp / 2
print(ans)
### BUGGY CODE ###

import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    cor_v = -1
    inc_v = 10 ** 20
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for v in a:
            cost += n - bisect.bisect_left(a, bin_v - v)
            if cost > m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = [0] + list(itertools.accumulate(a))
    c = 0
    t = 0
    for v in a:
        p = bisect.bisect_left(a, cor_v - v)
        c += n - p
        t += acm[-1] - acm[p] + v * (n - p)
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    cor_v = a[0] * 2
    inc_v = a[-1] * 2 + 1
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n-1, -1, -1):
            cost += n - bisect.bisect_left(a, bin_v - a[i])
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = list(itertools.accumulate([0] + a))
    t = 0
    c = 0
    for i in range(n):
        p = bisect.bisect_left(a, cor_v - a[i])
        t += acm[-1] - acm[p] + a[i] * (n - p)
        c += n - p
    print(t - (c - m) * cor_v)


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

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

inf = 10**10
ans = [[inf, inf, inf] for i in range(N+1)]

q = [S]
ans[S][0] = 0
while q:
    now = q.pop()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)
### BUGGY CODE ###

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

S=B-A

n=len(bin(S))-2

T=2**n

newA=A+(S//T)*T

x=newA

for i in range(newA+1,B+1):
    x=x^i

print(x)

### FIXED CODE ###

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

a=A%4
b=B%4

ans=0
cnt=0
for i in range(a,4):
    ans=ans^(A+cnt)
    cnt+=1
cnt=0
for i in range(b,-1,-1):
    ans=ans^(B-cnt)
    cnt+=1
print(ans)