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

import sys
import itertools
#import numpy as np
stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = rl()

B = [x+y for x, y in list(itertools.product(A, A))]
B.sort(reverse=True)

answer = sum(B[:M])
print(answer)


### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
A.sort()

def shake_cnt(x):
    Y = np.searchsorted(A,x-A)
    return N*N - Y.sum()

right = 10 ** 6
left = 0 #握手するのがM人以上
while right > left + 1:
    mid = (left+right) // 2
    if shake_cnt(mid) >= M:
        left = mid
    else:
        right = mid

X = np.searchsorted(A, right-A) #握手しない人数
Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()

shake = N*N - X.sum()
happy = (Acum[-1] - Acum[X]).sum() + (A * (N-X)).sum()
happy += (M-shake) * left
print(happy)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
                   
K, S = map(int, input().split())
cnt = 0

for X in range(0, K+1):
     for Y in range(0, K+1):
         for Z in range(0, K+1):
             SUM = X + Y + Z
             if SUM == S:
                 cnt += 1
print(cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-
                   
K, S = map(int, input().split())
cnt = 0

for X in range(0, K+1):
     for Y in range(0, K+1):
         if 0<=S-X-Y and S-X-Y<=K:
             cnt += 1
print(cnt)
### BUGGY CODE ###

#a_1+a_2+...+a_N = M   Find greatest common divisor of a
N,M=map(int,input().split())

Q=M//N #Quotient
R=M%N  #Reminder
'''
if Q>R :
    k=int((Q-R)//(1+N))
    k-=1
    Q -= k
    R += k*N
    '''
memo=0
while R%Q != 0:
    k= int(Q//(N+R//Q+1))   #max k:k*(N+R//Q)<Q-k
    #print(R,Q,R%Q,R//Q,k)
    while (R+k*N)//(Q-k) != memo and k >= 0:
        k -= 1
        #print(k,memo,(R+k*N)//(Q-k))
    if k > 0:
        Q -= k
        R += k*N
        memo=R//Q
    else:
        Q -= 1
        R += N
        memo=R//Q

print(Q)

### FIXED CODE ###

#a_1+a_2+...+a_N = M   Find greatest common divisor of a
N,M=map(int,input().split())

Q=M//N #Quotient
R=M%N  #Reminder
'''
if Q>R :
    k=int((Q-R)//(1+N))
    k-=1
    Q -= k
    R += k*N
    '''
memo=0
while R%Q != 0:
    k= int((Q-R%Q)//(N+R//Q+1))   #max k:k*(N+R//Q)<Q-k
    #print(R,Q,R%Q,R//Q,k)
    while (R+k*N)//(Q-k) > memo:
        k -= 1
        #print(k,memo,(R+k*N)//(Q-k))
    if k > 0:
        Q -= k
        R += k*N
        memo=R//Q
    else:
        Q -= 1
        R += N
        memo=R//Q

print(Q)
### BUGGY CODE ###

from scipy.sparse import*
f=csgraph.johnson
t=map(int,open('/dev/fd/0').read().split())
n,m,l=t[:3]
m=m*3+3
for i in f(f(csr_matrix((t[5:m:3],(t[3:m:3],t[4:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]]:print min(n,i)%n-1

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

import sys

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

ans = 0

for i in range(3,n):
	for j in range(i-2):
		for k in range(j+1,i):
			if s[i] != s[j] != s[k] != s[i]:
				if k - j != i - k:
					ans += 1

print(ans)


### FIXED CODE ###

import sys
import bisect
readline = sys.stdin.readline

def main():
	n = int(input())
	s = tuple(input())

	ans = 0
	r = []
	g = []
	b = []
	for i in range(3):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

	for i in range(3,n):
		if s[i] == 'R':
			r.append(i)
		elif s[i] == 'G':
			g.append(i)
		else:
			b.append(i)

		for j in range(i-2):
			if (j-i) % 2 == 0:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)
					index = bisect.bisect_left(r,j + (i-j)//2 )
					if index < len(r):
						if r[index] == j + (i-j)//2:
							ans -= 1
				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)
					index = bisect.bisect_left(g,j + (i-j)//2 )
					if index < len(g):
						if g[index] == j + (i-j)//2:
							ans -= 1
				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)
					index = bisect.bisect_left(b,j + (i-j)//2 )
					if index < len(b):
						if b[index] == j + (i-j)//2:
							ans -= 1
			else:
				if s[i] == s[j]:
					continue
				elif 'R' not in [s[i],s[j]]:
					ans += bisect.bisect_left(r,i) - bisect.bisect_left(r,j)

				elif 'G' not in [s[i],s[j]]:
					ans += bisect.bisect_left(g,i) - bisect.bisect_left(g,j)

				elif 'B' not in [s[i],s[j]]:
					ans += bisect.bisect_left(b,i) - bisect.bisect_left(b,j)


	print(ans)

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

import sys
input = sys.stdin.readline

def make_divisors(n):
    div_num = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div_num += 1
            if i != n // i:
                div_num += 1
    return div_num

n = int(input())
count = 0
for i in range(1, n):
  count += make_divisors(i)
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def make_divisors(n):
    div_num = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div_num += 1
            if i != n // i:
                div_num += 1
    return div_num

ans = [1166714, 2472071, 3829761, 5221424, 6638407, 8075420, 9529244, 10997400, 12478098]

n = int(input())
keta = 0
for j in range(1, 10+1):
  if n <= j*100000:
    keta = j-1
    break
if keta == 0:
  count = 0
else:
  count = ans[keta-1]
for i in range(max(keta*100000,1), n):
  count += make_divisors(i)
print(count)
### BUGGY CODE ###

N,K=map(int,input().split())
ans=0
if N<=K:
  pass
else:
  A=list(map(int,input().split()))
  for i in range(N-K):
    ans+=min(A)
    A.remove(min(A))  
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ans=0
if N<=K:
  pass
else:
  A=list(map(int,input().split()))
  A.sort()
  ans=sum(A[:N-K])
print(ans)
### BUGGY CODE ###

# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))

def mysub(a, b): return a - b if a > b else b - a

import heapq

pq = []
d = [0] * N
prev = [None] * N

heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7

while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if d[u] + cost < d[v]:
            d[v] = d[u] + cost
            heapq.heappush(pq, (d[v], v))
            prev[v] = u

print(d[-1])

### FIXED CODE ###

# encoding: utf-8
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
def mysub(a, b): return a - b if a > b else b - a
 
import heapq
 
pq = []
d = [0] * N
prev = [None] * N
 
heapq.heappush(pq, (0, 0))
for i in range(1, N): d[i] = 10 ** 9 + 7
 
while len(pq) > 0:
    Qu, u = heapq.heappop(pq)
    if Qu > d[u]: continue
    for i in range(1, min(K + 1, N - u)):
        v = u + i
        cost = mysub(h[u], h[v])
        if Qu + cost < d[v]:
            d[v] = Qu + cost
            heapq.heappush(pq, (Qu + cost, v))
            prev[v] = u
 
print(d[-1])
### BUGGY CODE ###

#from itertools import combinations as c

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
#for i, j in c(range(N), 2):
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

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

N=int(input())
S=tuple(input())
Q=int(input())
K=map(int,input().split())

for k in K:
    ans=0
    d=m=dm=0
    for i in range(N):
        c=S[i]
        if c=='D':
            d+=1
        elif c=='M':
            m+=1
            dm+=d
        elif c=='C':
            ans+=dm
        if i>=k-1:
            c=S[i-(k-1)]
            if c=='D':
                d-=1
                dm-=m
            elif c=='M':
                m-=1
    print(ans)

### FIXED CODE ###

N=int(input())
S=tuple(map(ord,input()))
Q=int(input())
K=map(int,input().split())
D,M,C=map(ord,'DMC')

for k in K:
    ans=0
    d=m=dm=0
    for i in range(min(k-1,N)):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
    for i in range(k-1,N):
        c=S[i]
        if c==D:
            d+=1
        elif c==M:
            m+=1
            dm+=d
        elif c==C:
            ans+=dm
        c=S[i-(k-1)]
        if c==D:
            d-=1
            dm-=m
        elif c==M:
            m-=1
    print(ans)
### BUGGY CODE ###

inpl = lambda: list(map(int,input().split()))
N = int(input())
rate = []
rate.append(inpl())
rate.append(inpl())
AB = []
BA = []
for i in range(3):
    rA, rB = rate[0][i], rate[1][i]
    if rB > rA:
        AB.append((rA, rB))
    elif rA > rB:
        BA.append((rB, rA))

dpAB = [0]*(N+1)
q = [0]*(len(AB)+1)
for i in range(1,N+1):
    k = 1
    for cost, ret in AB:
        if i >= cost:
            q[k] = dpAB[i-cost] + ret
            k += 1
    dpAB[i]=max(dpAB[i-1]+1, max(q))

M = dpAB[N]
dpBA = [0]*(M+1)
q = [0]*(len(BA)+1)
for i in range(1,M+1):
    k = 1
    for cost, ret in BA:
        if i >= cost:
            q[k] = dpBA[i-cost] + ret
            k += 1
    dpBA[i] = max(dpBA[i-1]+1, max(q))

print(dpBA[M])

### FIXED CODE ###

from fractions import gcd
from functools import reduce
inpl = lambda: list(map(int,input().split()))
def lcm(a,b):
    return a*b//gcd(a,b)
def lcm_list(numbers):
    return reduce(lcm, numbers)

N = int(input())
rate = []
rate.append(inpl())
rate.append(inpl())
AB = []
BA = []
for i in range(3):
    rA, rB = rate[0][i], rate[1][i]
    if rB > rA:
        AB.append((rA, rB))
    elif rA > rB:
        BA.append((rB, rA))
for l in [AB, BA]:
    l.sort(key=lambda x: -x[1]/x[0])

def buy_and_sell(N, cost_ret):
    if len(cost_ret) == 0:
        return N
    else:
        Nunit = lcm_list([ x[0] for x in cost_ret ])
        b0, s0 = cost_ret[0]
        q = N // b0
        n = max(0, q - 2*Nunit//b0 + 1)
        Ndp = N - n*b0
        dp = [0]*(Ndp+1)
        w = [0]*(len(cost_ret)+1)
        for i in range(1,Ndp+1):
            k = 1
            for cost, ret in cost_ret:
                if i >= cost:
                    w[k] = dp[i-cost] + ret
                    k += 1
            dp[i] = max(dp[i-1]+1, max(w))
        return s0*n + dp[-1]

M = buy_and_sell(N, AB)
L = buy_and_sell(M, BA)
print(L)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()

for i in range(1,n//2+1)[::-1]:
    d = deque([])
    for j in range(i,n-i+1):
        d.append(s[j:j+i])
    for j in range(n-2*i+1):
        tmp = s[j:j+i]
        ll = len(d)
        for k in range(ll):
            ddd = d.popleft()
            if tmp == ddd:
                print(i)
                quit()
            d.append(ddd)
        d.popleft()
print(0)



### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1; j = 0
    A[0] = l = N
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
res = 0
for i in range(n):
    c = z_algo(s[i:])
    # print(c)
    for j,t in enumerate(c):
        tmp = min(j,t)
        res = max(res, tmp)
print(res)
### BUGGY CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**19):
  b.append(format(i,'0'+str(19)+'b'))
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

for i in range(n):
  y=copy.copy(x)
  y[i]=str(1-int(y[i]))
  ct1=0
  for j in range(n):
    if y[j]=='1':
      ct1+=1
  
      
  if ct1==0:
    print(0)
  else:
    z=0
    y.reverse()
    for j in range(n):
      if y[j]=='1':
        z+=pow(2,j,ct1)
        z%=ct1
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

### FIXED CODE ###

import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)
### BUGGY CODE ###

from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

### FIXED CODE ###

from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

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

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###

n,m = map(int,input().split())
l1 = list(map(int,input().split()))

for i in range(m):
  l1 = sorted(l1)
  l1[-1] //= 2
print(sum(l1))
  

### FIXED CODE ###

import heapq 
n,m = map(int,input().split())
l = list(map(int,input().split()))
l1 = [-i for i in l]
heapq.heapify(l1)

for i in range(m):
  a = heapq.heappop(l1)
  b = -(-a//2)
  heapq.heappush(l1,b)
print(sum(l1)*-1)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort_left(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            k = -1
            for h in heads:
                if h > a:
                    k = h
                    break
            heads.remove(k)
            bi.insort_left(heads, a)
        else:
            bi.insort_left(heads, a)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import bisect as bi


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    bi.insort(heads, a)
    while A:
        a = A.pop()
        if a < heads[-1]:
            j = bi.bisect(heads, a)
            del heads[j]
        bi.insort(heads, a)
    return len(heads)
  

def main():
    print(solve())


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

n=int(input())

ans =0
for i in range(2,int(n**0.5)+5):
    cnt = 0
    while n%i==0:
        n//=i
        cnt += 1
        s=0
    while cnt:
        s +=1
        cnt -= s
        ans += 1
if n!=1:ans+=1
print(ans)

### FIXED CODE ###

n=int(input())

ans =0
for i in range(2,int(n**0.5)+5):
    cnt = 0
    while n%i==0:
        n//=i
        cnt += 1
    s=1
    while cnt-s>=0:
        cnt -= s
        s +=1
        ans += 1
if n!=1:ans+=1
print(ans)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

n=int(input())
d = list(map(int,input().split()))
cnt=0

d.sort()
a=d[0]
b=d[n-1]
c=b-a+1

for i in range(c):
    index=bisect.bisect_right(d,i+a)
    D=d[index:]
    lend=len(D)
    if(int(n//2)==lend):
        cnt+=1
    

print(cnt)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n=int(input())
    d = list(map(int,input().split()))
    cnt=0

    d.sort()
    a=d[(n//2)-1]
    b=d[(n//2)]
    ans=b-a
    print(ans)
    
main()
### BUGGY CODE ###

import numpy
n=int(input())
l=numpy.array(list(map(int, input().split())))
a=l.prod()
c=0
while a%2==0:
    a//=2
    c+=1
print(c)

### FIXED CODE ###

import numpy
n=int(input())
l=list(map(int, input().split()))
c=0
for i in range(n):
    a=l[i]
    while a%2==0:
        a//=2
        c+=1
print(c)
### BUGGY CODE ###

from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

for _ in range(M):
    a.append(int(input()))

MOD = 1000000007

dict = defaultdict(int)
ans = 1
dict[0] = 1
for i in range(N):
    if not a.count(i + 1):
        dict[i + 1] += dict[i]
    if not a.count(i + 2):
        dict[i + 2] += dict[i]
    if a.count(i + 1) and a.count(i + 2):
        print("0")
        exit()


print(dict[N] % MOD)




### FIXED CODE ###

from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

for _ in range(M):
    a.append(int(input()))

MOD = 1000000007

dict = defaultdict(int)

for i in range(M):
    if i >= 1 and a[i] - a[i - 1] == 1:
        print("0")
        exit()

dict[0] = 1
a_s = set(a)
for i in range(N):
    if not i in a_s:
        dict[i + 1] += dict[i]
        dict[i + 2] += dict[i]


print(dict[N] % MOD)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
i_count = 0

for i in range(N):
  if P[i] == min(P[:i+1]):
    i_count += 1

print(i_count)


### FIXED CODE ###

N = int(input())
P = [int(e) for e in input().split()]
i_count = 0
min_P = 200001

for i in range(N):
  if min_P > P[i]:
    min_P = P[i]
    i_count += 1

print(i_count)
### BUGGY CODE ###

n, k = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
dp = [0]*(n+1)
dp[1] = 1
mod = 998244353

for i in range(2, n+1):
    for j in range(k):
        li = max(i-s[j][1], 1)
        ri = i-s[j][0]
        if ri < 0:
            continue
        dp[i] += sum(dp[li: ri+1])
        dp[i] %= mod
print(dp[n])
    


### FIXED CODE ###

n, k = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(k)]
dp = [0]*(n+1)
dp[1] = 1
mod = 998244353
dpsum = [0]*(n+1)
dpsum[1] = 1

for i in range(2, n+1):
    for j in range(k):
        li = max(i-s[j][1], 1)
        ri = i-s[j][0]
        if ri < 0:
            continue
        dp[i] += dpsum[ri]-dpsum[li-1]
        dp[i] %= mod
    dpsum[i] = dpsum[i-1]+dp[i]
print(dp[n])
### BUGGY CODE ###

import sys
import math


# input = sys.stdin.readline

def binary_search(arr, key,j):
    ok = j
    ng = len(arr)

    while abs(ok - ng) > 1:
        mid = int((ok + ng) / 2)

        if arr[mid] < key:
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans =0
    for i in range(N-2):
        for j in range(i+1,N-1):
            ok = binary_search(L,L[i]+L[j],j)
            ans += ok-j
    print(ans)
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#import math


# input = sys.stdin.readline

def binary_search(arr, key,j):
    ok = j
    ng = len(arr)

    while abs(ok - ng) > 1:
        mid = int((ok + ng) / 2)

        if arr[mid] < key:
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans =0
    for i in range(N-2):
        for j in range(i+1,N-1):
            ok = binary_search(L,L[i]+L[j],j)
            ans += ok-j
    print(ans)
if __name__ == "__main__":
    main()