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

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

MOD = 10**9+7

n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = int_to_bits(a)
    a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    bits_dash = [ bits[i] - a_bits[i] for i in range(60)]

    # log("bits_dash", bits_dash)

    for i in range(60):
        ans += 2**i * abs(bits_dash[i] - a_dash[i])
    # log(a, ans)

print((ans//2) % MOD)


### FIXED CODE ###

import sys
import time

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

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

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)
### BUGGY CODE ###

import copy

S = list(input())
ans = ['1'] * len(S)
# split_num = [0]
# for i, s in enumerate(S[1:-1]):
#     if S[i-1] == "L" and S[i+1] == "R":
#         ans[i] = 0
#         split_num.append(i)
# split_num.append(len(S))
# #
# for i in range(len(split_num)-1):
#     for i, s in enumerate(S[split_num[i]:split_num[i+1]]):
#         print(s)

pre_ans = ['1'] * len(S)
pre_pre_ans = ['1'] * len(S)
flag = 0
# while True:
for k in range(1, 10 ** 10):
    ans[0] = '0'
    ans[-1] = '0'
    if S[1] == 'L':
        ans[0] = pre_ans[1]
    if S[-2] == "R":
        ans[-1] = pre_ans[-2]
    for i, s in enumerate(S[1:-1]):
        ans[i+1] = '0'
        if S[i] == 'R' and S[i+2] == "L":
            ans[i+1] = str(int(pre_ans[i]) + int(pre_ans[i+2]))
        elif S[i] == 'R':
            ans[i+1] = pre_ans[i]
        elif S[i+2] == 'L':
            ans[i+1] = pre_ans[i+2]
    if ans == pre_ans:
        flag = 1
        break
    elif ans == pre_pre_ans:
        if k % 2 == 0:
            flag = 1
        else:
            flag = 2
        break
    pre_pre_ans = copy.deepcopy(pre_ans)
    pre_ans = copy.deepcopy(ans)

if flag == 1:
    print(' '.join(ans))
elif flag == 2:
    print(' '.join(pre_ans))


### FIXED CODE ###

s = input()
tmp = [0]
for i in range(len(s)-1):
    if s[i] != s[i+1]:  # RとLが切り替わる時のインデックスを保存
        tmp.append(i+1)
tmp.append(len(s))
ans = [0 for i in range(len(s))]
for i in range(len(tmp)-1):
    if i % 2 == 1:
        ans[tmp[i]] = (tmp[i]-tmp[i-1])//2 + (tmp[i+1]-tmp[i]+1)//2
        ans[tmp[i]-1] = (tmp[i+1]-tmp[i])//2 + (tmp[i]-tmp[i-1]+1)//2
print(*ans)
# RRLLLLRLRRLL
### BUGGY CODE ###

n=int(input())
a=tuple(map(int,input().split()))
for cnt,val in enumerate(a):
    print(len([j for j in a[cnt:] if j==cnt+1]))
print(0)


### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)
for n in range(N):
  print(count[n+1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 10**10
for i in range(1,n):
    m = min(m, abs(sum(a[:i])-sum(a[i:])))
print(m)

### FIXED CODE ###

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

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
gcd_list=[]
i=int(input())
for x in range(1, i+1):
  for y in range(1, i+1):
    for z in range(1, i+1):
      gcd_list.append(gcd(x, y, z))
      
print(sum(gcd_list))

### FIXED CODE ###

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)
### BUGGY CODE ###

import heapq
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    heapq.heappush(path,(abs(y-y2),i,j))
union = [[i] for i in range(N)]
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = heapq.heappop(path)
    if union[i] is union[j]:continue
    while union[j]:
        k = heapq.heappop(union[j])
        union[k] = union[i]
        heapq.heappush(union[i],k)
    ans += c
    cnt += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)
### BUGGY CODE ###

#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

#Warshall-Floyd
def w_f():
    inf=10**9
    d=[[inf]*V for i in range(V)]
    for i in range(V):
        d[i][i]=0

    for i in range(E):
        fr, to, co=map(int,input().strip().split(' '))
        d[fr-1][to-1]=co
        d[to-1][fr-1]=co
    for i in range(V):
        for j in range(V):
            for k in range(V):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d


dist=w_f()

ans=inf

def dfs(i,p,d):
    global ans
    if i==R:
        if d<ans:
            ans=d
        return
    for j in range(R):
        if visited[j]==False:
            visited[j]=True
            if p==-1:
                dfs(i+1,j,0)
            else:
                #print(rlis[p]-1,rlis[i]-1)
                dfs(i+1,j,d+dist[rlis[p]-1][rlis[j]-1])
            visited[j]=False

            
visited=[False]*V

dfs(0,-1,0)
            
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

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

n, k = map(int, input().split())
p = list(map(lambda x: (1 + x) / 2, map(int, input().split())))

ans = max(sum(p[i:i+k]) for i in range(n - k + 1))
print(ans)


### FIXED CODE ###

from itertools import accumulate

n, k = map(int, input().split())
p = map(int, input().split())

ac = [0] + list(accumulate(map(lambda x: (1 + x) / 2, p)))
ans = max(ac[i+k] - ac[i] for i in range(n - k + 1))
print(ans)
### BUGGY CODE ###

import numpy
S = numpy.array([0 if s == 'B' else 1 for s in input()])

ans = 0
for i in numpy.where(S == 1)[0]:
    ans += numpy.count_nonzero(S[:i] == 0)
print(ans)

### FIXED CODE ###

import numpy
from numpy.core.defchararray import count
S = numpy.array([0 if s == 'B' else 1 for s in input()])

count = 0
bcount = 0

for i, s in enumerate(S):
    if s == 0:
        bcount += 1
    else:
        count += bcount

print(count)
### BUGGY CODE ###

N = int(input())

start = 0
end = N

print(0)
s0 = input()
if s0 == 'Vacant':
    exit()

ni = (start+end)//2
print(ni, flush=True)
s = input()

while s != 'Vacant':
    if not((s == s0) ^ ((s % 2) == (s0 % 2)):
        start = ni
    else:
        end = ni

    s0 = s

    ni = (start+end)//2
    print(ni, flush=True)
    s = input()


### FIXED CODE ###

N = int(input())


def ask(i):
    print(i, flush=True)
    resp = input()
    if resp == 'Vacant':
        exit()
    return resp


def test(l, r, l_resp, r_resp):
    if l % 2 == r % 2:
        return l_resp == r_resp
    else:
        return l_resp != r_resp


resp = ask(0)

l = 0
r = N
l_resp = resp
r_resp = resp

for _ in range(19):
    m = (l+r)//2
    m_resp = ask(m)
    if test(l, m, l_resp, m_resp):
        l, l_resp = m, m_resp
    else:
        r, r_resp = m, m_resp
### BUGGY CODE ###

import sys

def check_ans(s,x):
  if len(s)==0 and x!=0:
    return False
  elif len(s)==0 and x==0:
    return True
  dp=[[False for i in range(8002)] for j in range(8002)]
  dp[1][s[0]]=True
  for i in range(1,len(s)):
    for j in range(0,8002):
      if dp[i][j]:
        res=abs(j+s[i])
        res2=abs(j-s[i])
        dp[i+1][res]=True
        dp[i+1][res2]=True
  return dp[len(s)][x]

S = sys.stdin.readline().strip()
X,Y=map(int,input().split())
d=1
while S and S[0]=='F':
  S=S[1:]
  X-=1
if len(S)==0:
  if X==0:
    print("Yes")
  else:
    print("No")
  sys.exit()

nx=[]
ny=[]
X=abs(X)
Y=abs(Y)

while S:
  step=0
  while S and S[0]=='T':
    d*=-1
    S=S[1:]
  while S and S[0]=='F':
    step+=1
    S=S[1:]
  if d==1:
    nx.append(step)
  else:
    ny.append(step)

if check_ans(nx,X) and check_ans(ny,Y):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys

def check_ans(s,x):
  res=[0]
  for i in s:
    res = set([x + i for x in res]) | set([x - i for x in res])
  return x in res

S = sys.stdin.readline().strip()
X,Y=map(int,input().split())
d=1
while S and S[0]=='F':
  S=S[1:]
  X-=1
if len(S)==0:
  if X==0 and Y==0:
    print("Yes")
  else:
    print("No")
  sys.exit()

nx=[]
ny=[]
X=abs(X)
Y=abs(Y)

while S:
  step=0
  while S and S[0]=='T':
    d*=-1
    S=S[1:]
  while S and S[0]=='F':
    step+=1
    S=S[1:]
  if step==0:
    break
  if d==1:
    nx.append(step)
  else:
    ny.append(step)

if check_ans(nx,X) and check_ans(ny,Y):
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=sorted(A)
print(' '.join([str(A.index(b)+1) for b in B]))


### FIXED CODE ###

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

d=[0 for n in range(N)]
for n in range(N):
    d[A[n]-1] = str(n+1)

print(" ".join(d))
### BUGGY CODE ###

n = int(input())
numbers = [int(x) for x in input().split()]
count = 0
while True:
  for i in range(n):
    if numbers[i] % 2 == 0:
      numbers[i] /= 2
    else:
      print(count)
      break
  count += 1

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            print(ans)
            exit()
    ans += 1
### BUGGY CODE ###

N, M, K = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(K)]
 
lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]
 
for a,b in ab:
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)
 
    
for c,d in cd:
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
 
groups = []
visiteds = [0]*N
c = 0

for i in range(N):
    if visiteds[i] == 1: continue

    temp = [i]
    visited = [i]
    visiteds[0] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
 
ans = [0]*N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

N, M, K = map(int, input().split())
 
lstab = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    lstab[a-1].append(b-1)
    lstab[b-1].append(a-1)

visited = [0] * N
cnt = 0

for i in range(N):
    if visited[i] != 0: continue
    temp = [i]
    cnt += 1
    visited[i] = cnt
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visited[y] != 0:continue
            temp.append(y)
            visited[y] = cnt

numcd = [ 0 ] * N
for _ in range(K):
    c, d = map(int, input().split())
    if visited[c-1] == visited[d-1]:
        numcd[c-1] += 1
        numcd[d-1] += 1    
    
ans = [0] * N
cnt = Counter(visited)

for i in range(N):
    ans[i] = cnt[visited[i]] - 1 - len(lstab[i]) - numcd[i]
 
print(*ans)
### BUGGY CODE ###

from operator import itemgetter

N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0] * (T+1) for i in range(N)]

dp[0][T] = data[0][1]
for i in range(1, N):
    time = data[i-1][0]
    value = data[i-1][1]
    add_value = data[i][1]
    for j in range(T):
        if j >= time:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time] + value)
        else:
            dp[i][j] = dp[i-1][j]
    dp[i][T] = max(dp[i][T-1] + add_value, dp[i-1][T])

print(dp[-1][-1])


### FIXED CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
for i in range(n):
  b=a[:]
  del b[i]
  print(max(b))

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
b=sorted(a)
for i in a:
  print(b[-2] if i==b[-1] else b[-1])
### BUGGY CODE ###

import math
k=int(input())
total=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for m in range(1,k+1):
            g=math.gcd(i,j)
            g=math.gcd(g,m)
            total+=g
print(total)

### FIXED CODE ###

import math
k=int(input())
total=0
info=[0]
for i in range(1,201):
    for j in range(1,201):
        if j<i:
            info.append(0)
            continue
        info.append(math.gcd(i,j))
        #print(str(i)+" "+str(j)+" "+str(math.gcd(i,j)))
#print(info[202])
#print(info)
for i in range(1,k+1):
    a=[]
    a.append(i)
    for j in range(1,k+1):
        a.append(j)
        for m in range(1,k+1):
            a.append(m)
            a=sorted(a)
            gcd=info[(a[0]-1)*200+a[1]]
            b=min(gcd,a[2])
            c=max(gcd,a[2])
            gcd=info[(b-1)*200+c]
            total+=gcd
            #print(gcd)
            #print(a)
            a=[i,j]
        a=[i]
print(total)
### BUGGY CODE ###

def sq(a, b, mod):  # aのb乗を剰余,kは初期値#20191116-D-Knight
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer

n = int(input())
alist = list(map(int, input().split()))
m = max(alist)
ans = 0
ans_ = (0, 0)
for a in alist:
    nck = nCk(m, a)
    if nck >= ans:
        # print(nck)
        ans = nck
        ans_ = (m, a)
print(ans_[0], ans_[1])


### FIXED CODE ###

n = map(int, input().split())
alist = list(map(int, input().split()))
m = max(alist)
sbn = 10**10
for a in alist:
    if abs(m/2 - a) < sbn and a != m:
        ans = a
        sbn = abs(m/2 - a)
print(m, ans)
### BUGGY CODE ###

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


def lcm(a, b):
    return a * b // gcd (a, b)


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort()
A = A[::-1]

l = A[0]
for a in A:
  if l%a != 0:
    l = lcm(l, a)

ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

### FIXED CODE ###

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


def lcm(a, b):
    return a * b // gcd (a, b)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

l %= MOD
ans = 0
for a in A:
  ans += (l * power(a, MOD-2)) % MOD
  ans %= MOD

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

n=int(input())
b=list(map(int,input().split()))
an=1
c=0
for m in b:
  an*=m
if(an>10**18):
  print("-1")
else:
  print(an)
  

### FIXED CODE ###

n=int(input())
b=list(map(int,input().split()))
b.sort()
an=1
c=0

for m in b:
  an*=m
  if(an>10**18):
    print("-1")
    c=1
    break
if(c!=1):
  print(an)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  pool.sort()
  try:
    #print(pool)
    ans -= heapq.heappop(pool)
    #print(pool)
  except:
    pass
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  try:
    #print(pool)
    ans -= heapq.heappop(pool)
    #print(pool)
  except:
    pass
print(ans)
### BUGGY CODE ###

from itertools import product
from math import gcd

k = int(input())

res = 0
for a, b, c in product(range(1, k+1), repeat=3):
    res += gcd(gcd(a, b), c)

print(res)


### FIXED CODE ###

from math import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)
### BUGGY CODE ###

import numpy as np

def test():
    n = int(input())
    a = np.array([int(x) for x in input().split()])
    m = max(a)
    ans = 0
    for x in range(m+1):
        ans = max(ans,sum(a==x+1)+sum(a==x)+sum(a==x-1))
    print(ans)


if __name__ == "__main__":
    test()


### FIXED CODE ###

import collections

def test():
    n = int(input())
    a = [int(x) for x in input().split()]
    b = collections.Counter(a)
    ans = 0
    for x in range(max(a)+1):
        ex = b[x]
        if x - 1 in b:
            ex += b[x-1]
        if x + 1 in b:
            ex += b[x+1]
        ans = max(ans,ex)

    print(ans)


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

from fractions import gcd
def lcm(x, y):
    return (x // gcd(x, y)) * y
MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))

l = 1
for i in A:
  l = lcm(l, i)
  
B = [(l // i) % MOD for i in A]

ans = sum(B) % MOD

print(ans)

### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
  return (x * y) // gcd(x, y)

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

l = 1
for i in A:
  l = lcm(l, i)
l %= MOD

ans = 0
for i in A:
  ans += l * pow(i, MOD - 2, MOD)
  ans %= MOD
print(ans)
### BUGGY CODE ###

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

k = [[0 for i in range(a[0])] for j in range(a[0])]

for i in range(a[1]):
    m,n = map(int,input().split())
    k[m-1][n-1] += 1

for i in range(a[2]):
    p = 0
    m,n = map(int,input().split())
    for j in range(m-1,n):
        for l in range(j,n):
            p += k[j][l]
    print(p)


### FIXED CODE ###

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

c = [[0 for i in range(a[0]+1)] for j in range(a[0]+1)]

for i in range(a[1]):
    n,m = map(int,input().split())
    c[n][m] += 1

d = [[0 for i in range(a[0]+4)] for j in range(a[0]+4)]

for i in range(a[0]+1):
    for j in range(a[0]+1):
        d[i][j+1] = d[i][j] + c[i][j]

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

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
i=1
while len(a)>=2:
    if i>=len(a)-1:
        i=1
    a[i]-=a[0]
    if a[i]<=0:
        del a[i]
    i+=1
    a.sort()

print(a[0])

### FIXED CODE ###


n=int(input())
a=[int(i) for i in input().split()]
c=a[0]
def gcd(x,y):
    while y:
        x,y=y,x%y
    return x

for i in a:
    c=gcd(c,i)
print(c)
### BUGGY CODE ###

N = int(input())
D = list(map(int, input().split()))
MOD = 998244353
ans = 1
x = [0] * N
for i in range(N):
  p = D[i]
  x[p] += 1 

if (D[0] != 0) or (x[0] != 1):
  ans = 0
  print(ans % MOD)
  quit()
  
fi = 0
for i in range(N-1):
  ans = ans * (x[i] ** x[i + 1])
  if x[i] == 0:
    fi = 1
  if (fi == 1) and (x[i] != 0):
    ans = 0
    print(ans)
    quit()
    
if (fi == 1) and (x[N-1] != 0):
  ans = 0
print(ans % MOD)

### FIXED CODE ###

import collections
N = int(input())
D = list(map(int, input().split()))
D_C = collections.Counter(D)
D_C = D_C.items()
D_C = sorted(D_C)

#print(D_C)
N = len(D_C)
MOD = 998244353
ans = 1

if (D[0] != 0) or (D_C[0][1] != 1):
  ans = 0
  print(ans % MOD)
  quit()
  
for i in range(N-1):
  ans = ans * (D_C[i][1] ** D_C[i + 1][1])
  if i > 0:
    if D_C[i][0] != x + 1:
      ans = 0
      print(ans)
      quit()
  x = D_C[i][0]

if D_C[N-1][0] != x + 1:
  ans = 0
print(ans % MOD)