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

import math

n = int(input())
a = [int(i) for i in input().split(" ")]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)

for i in range(1, n + 1):
    s[i] = a[i] + s[i - 1]
    sr[i] = ar[i] + sr[i - 1]
    
def bs(s, l, r, rr):
    if l == r:
        return l
    else:
        h = math.ceil((l + r) / 2)
        if s[h] * 2 > s[rr]:
            return bs(s, l, h - 1, rr)
        else:
            return bs(s, h, r, rr)
        
def min_2(s, i, rr):
    a = abs(s[i] - (s[rr] - s[i]))
    b = abs(s[i + 1] - (s[rr] - s[i + 1]))
    if a <= b:
        return i
    else:
        return i + 1
    
def f(a):
    return max(a) - min(a)

m_min = 2 * 10**14
for i in range(2, n - 1):
    pq = bs(s, 1, i, i)
    rs = bs(sr, 1, n - i, n - i)
    pq = min_2(s, pq, i)
    rs = min_2(sr, rs, n - i)
    m = f([s[pq], s[i] - s[pq], sr[rs], sr[n - i] - sr[rs]])
    if m < m_min:
        m_min = m
        
print(m_min)

### FIXED CODE ###

import math

n = int(input())

a = [int(i) for i in input().split(" ")]
ar = a[::-1]
a = [0] + a
ar = [0] + ar
s = [0] * (n + 1)
sr = [0] * (n + 1)
li = 0
ri = n

for i in range(1, n + 1):
    s[i] = a[i] + s[i - 1]
    sr[i] = ar[i] + sr[i - 1]
    
def f(a):
    return max(a) - min(a)

def fs(rr):
    global li
    while abs(s[rr] - 2 * s[li]) > abs(s[rr] - 2 * s[li + 1]):
        li += 1
        
def fsr(rr):
    global ri
    while abs(sr[rr] - 2 * sr[ri]) > abs(sr[rr] - 2 * sr[ri - 1]):
        ri -= 1

m_min = 2 * 10**14
for i in range(2, n - 1):
    fs(i)
    fsr(n - i)
    m = f([s[li], s[i] - s[li], sr[ri], sr[n - i] - sr[ri]])
    if m < m_min:
        m_min = m
        
print(m_min)
### BUGGY CODE ###

n = int(input())
total = [0] * (n + 1)
ans = set()
num = float('inf')
for i in range(1, n + 1):
    total[i] = total[i - 1] + i
for i in range(1, n + 1):
    if total[i] >= n:
        num = i
        break
remove_num = total[i] - n
for i in range(1, num + 1):
    if i != remove_num:
        ans.add(i)
print(*ans, sep='\n')

### FIXED CODE ###

n = int(input())
ans = set()
num = float('inf')
total = 0
for i in range(1, n + 1):
    total += i
    if total >= n:
        num = i
        break
remove_num = total - n
for i in range(1, num + 1):
    if i != remove_num:
        ans.add(i)
print(*ans, sep='\n')
### BUGGY CODE ###

s = input()
K = int(input())
strs = [[] for _ in range(26)]

for ind,i in enumerate(s):
    for j in range(1,len(s)-ind+1):
        st = s[ind:ind+j]
        if(not st in strs[ord(i)-97]):
            strs[ord(i)-97].append(st)


cnt = 0
num = 0
while(cnt<K):
    cnt += len(strs[num])
    num += 1
num -= 1
cnt -= len(strs[num])
strs[num].sort()
print(strs[num][K-cnt-1])


### FIXED CODE ###

s = input()
K = int(input())
strs = [[] for _ in range(26)]
cnts = [0]*26

for ind,i in enumerate(s):
    if(sum(cnts[:ord(i)-97])>=5):
        continue
    for j in range(1,K+1):
        st = s[ind:ind+j]
        if(not st in strs[ord(i)-97]):
            strs[ord(i)-97].append(st)
            cnts[ord(i)-97]+=1


cnt = 0
num = 0
while(cnt<K):
    cnt += len(strs[num])
    num += 1
num -= 1
cnt -= len(strs[num])
strs[num].sort()
print(strs[num][K-cnt-1])
### BUGGY CODE ###

from itertools import combinations as C

n = int(input())
A = list(map(int, input().split()))
q = int(input())
query = list(map(int, input().split()))

def check(m):
    for r in range(1, n + 1):
        for sub in C(A, r):
            if sum(sub) == m:
                return True
    return False

for m in query:
    if check(m):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
query = list(map(int, input().split()))

@lru_cache(maxsize=None)
def solve(i, m):
    if m == 0:
        return True
    elif i >= n or m < A[i]:
        return False
    else:
        return solve(i + 1, m - A[i]) or solve(i + 1, m)

for m in query:
    if solve(0, m):
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

def solve(a,b):
    l = len(bin(b)) - 2
    count = (b - a + 1)
    
    ans = 0

    for n in range(1,l+1):
        r = count % (2 ** n)
        b = 0
        if n == 1:
            if (count // 2) % 2 != 0:
                b = 1
        for j in range(a,a+r):
            b += ((j >> (n - 1)) & 1)
        if b % 2 == 1:
            ans += 1 << (n - 1)
    print(ans)

a,b = map(int, input().split())
solve(a,b)

### FIXED CODE ###

def solve(a,b):
    l = []
    count = (b - a + 1)
    r = 0
    if (a % 2 != 0):
        l.append(a)
        r += 1
    if (b % 2 == 0):
        l.append(b)
        r += 1
    if ((count - r) / 2) % 2 != 0:
        l.append(1)

    ans = 0
    for n in l:
        ans = ans ^ n
    print(ans)

a,b = map(int, input().split())
solve(a,b)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

ship = []
count = 0

for i in range(m):
    if ab[i][1] == n:
        ship.append(ab[i])

for j in range(len(ship)):
    for i in range(m):
        if ab[i][1] == ship[j][0] and ab[i][0] == 1:
            print('POSSIBLE')
            count += 1
            break

if count == 0:
    print('IMPOSSIBLE')


### FIXED CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

ship_list1 = []
ship_list2 = []
count = 0
loop = False

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i][1])
    if ab[i][1] == n:
        ship_list2.append(ab[i][0])

if len(set(ship_list1) & set(ship_list2)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

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

### FIXED CODE ###

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

import sys
input = sys.stdin.readline

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
 
  ans = 0
  for i in range(60):
    count_one = sum(a>>i & 1 for a in A)
    ans += count_one * (N - count_one) * pow(2, i)
 
  print(ans%MOD)
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

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

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

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

N = int(input())
seq = list(map(int,input().split()))
ans = "YES"

for i in range(N):
    for j in range(i+1, N):
        if seq[i] == seq[j]:
            ans = "NO"
            break
    if ans == "NO":
        break

print(ans)

### FIXED CODE ###

N = int(input())
seq = list(map(int,input().split()))
ans = "YES"

seq.sort()

for i in range(N-1):
    if seq[i] == seq[i+1]:
        ans = "NO"
        break


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

n = int(input())
a = list(map(int, input().split()))
d = set(a)
s = sum(a)
l = [0]*(10**5)
p = []
for i in d:
    l[i-1] = a.count(i)
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    s = s + l[b-1]*(c-b)
    l[c-1] += l[b-1]
    l[b-1] = 0
    p.append(s)
for i in p:
    print(i)

### FIXED CODE ###

from collections import Counter

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

counter = Counter(a)
sum_res = sum(a)  # はじめの合計、名前がsumだとsum関数とかぶってよくないので

# q回操作します。ループ変数は使わないので_とします（Pythonの慣習）
for _ in range(q):
    before, after = map(int, input().split())

    # 合計を変更します
    sum_res -= before * counter[before]
    sum_res += after * counter[before]

    # 個数を変更します
    counter[after] += counter[before]
    counter[before] = 0

    print(sum_res)
### BUGGY CODE ###

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        
        if reduce(operator.mul,ANS[a[1]:a[1]+L])!=0 : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == INIT:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == INIT : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == INIT : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.995
INIT = 0
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

H, W, K = map(int,input().split())
sth,stw,glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(init,glh,glw):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        for d in direc:
            for sk in range(1,K+1):
                hs, ws = h + d[0]*sk, w + d[1]*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                    next_q.append([hs,ws])
                    Dist[hs][ws] = Dist[h][w] + 1
                if hs==glh and ws==glw:
                    return Dist[hs][ws]
    return -1

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q,glh,glw)
    print(ret)


if __name__ == '__main__':
    main()

### FIXED CODE ###

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

H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

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

#pragma GCC optimize("Ofast")

a=int(input())

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


w=[]

for i in range(a-1):
  for j in range(i+1,a):
    w.append(d[i]*d[j])

sum=sum(w)
mod = pow(10,9)+7
print(pow(sum,1,mod))

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

total=sum(alst)
sum=0

# for i in range(n-1):
#   for j in range(i+1,n):
#     sum=pow(sum+alst[i]*alst[j],1,MOD)

# print(sum)

for a in alst:
  sum = sum+a * (total - a)
  sum %= MOD

sum *= pow(2, MOD - 2, MOD)
sum %= MOD
print(sum)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m): a.append(a.pop(a.index(max(a)))//2)
print(sum(a))

### FIXED CODE ###

import heapq as hq
n, m = map(int, input().split())
a = []
for i in input().split(): hq.heappush(a, -int(i))
for i in range(m): hq.heappush(a, int(hq.heappop(a)/2))
print(-sum(a))
### BUGGY CODE ###

import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))

a1 = a + 1
a2 = a - 1

lst = np.concatenate([a, a1, a2], 0)
lst = list(lst)

set_lst = list(set(lst))
ans = 0
for i in set_lst:
    tmp = lst.count(i)
    if tmp > ans:
        ans = tmp

print(ans)

### FIXED CODE ###

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

cnt = [0] * 1000010
for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i-1] += 1

print(max(cnt))
### BUGGY CODE ###

L,R=map(int, input().split())
#2019の倍数が入っていれば０→R-Lが２０１９以上
if L-R>=2019:
    print(0)
    exit()

ans=2019
for i in range(L,R):
    for j in range(i+1,R+1):
        ans=min(ans, (i*j)%2019)
print(ans)

### FIXED CODE ###

L,R=map(int, input().split())
#2019の倍数が入っていれば０→R-Lが２０１９以上
if R-L>=2019:
    print(0)
    exit()

ans=2019
for i in range(L,R):
    for j in range(i+1,R+1):
        ans=min(ans, (i*j)%2019)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
toko=[]
for i in range(1,N+1):
    toko.append(A.index(i)+1)

print(' '.join(list(map(str,toko))))


### FIXED CODE ###

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

tmp=list(enumerate(A))
tmp.sort(key=lambda x: x[1])
b = [str(x[0]+1) for x in tmp]
print(' '.join(b))
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)

count=0
for i in range(0,n-2):
    k=L[i]
    for j in range(i+1,n-1):
        t=L[j]
        if k>=t+L[j+1]:
            break
        for m in range(j+1,n):
            if k>=t+L[m]:
                break
            else:
                count+=1
print(count)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
def nibuta(a,x):
    h=len(a)
    if a[0]>=x:
        return 0
    elif a[h-1]<x:
        return h
    else:
        lo=-1
        up=h-1
        while up-lo>1:
            if a[(lo+up)//2]>=x:
                up=(lo+up)//2
            else:
                lo=(lo+up)//2
        if a[up]>=x:
            return lo+1
        else:
            return up+1
s=0
for i in range(n-2):
    a1=l[i]
    for j in range(i+1,n-1):
        k=a1+l[j]
        s=s+nibuta(l[j+1:],k)
print(s)
### BUGGY CODE ###

N = int(input())
An = list(map(int,input().split()))
c = 0
Bn = []
Cn = []
Bn = Bn + An
Cn = Cn + An
for k in range(N):    
    Bn[k] = Bn[k] + k + 1
    Cn[k] = k + 1 - Cn[k]
for X in range(1,N):
    if X in Bn and X in Cn:
        c = c + Bn.count(X) * Cn.count(X)
print(c)

### FIXED CODE ###

from collections import Counter
N = int(input())
An = list(map(int,input().split()))
c = 0
Bn = []
Cn = []
for k in range(N):    
    Bn.append(An[k]+k)
    Cn.append(k-An[k])
Cj = Counter(Cn)
for i in Bn:
    c+=Cj[i]
print(c)
### BUGGY CODE ###

n,m = map(int,input().split())
l = []
r = []

while True:
  try:
    tl,tr = map(int,input().split())
    l.append(tl)
    r.append(tr)
  except:
    break

l = sorted(l)
r = sorted(r)
cnt = 0
for i in range(1,n+1):
  if i>=max(l) and i<=min(r):
    cnt +=1
    
print(cnt)
    

### FIXED CODE ###

n,m = map(int,input().split())
l = []
r = []

while True:
  try:
    tl,tr = map(int,input().split())
    l.append(tl)
    r.append(tr)
  except:
    break

R = min(r)
L = max(l)
cnt = 0
for i in range(1,n+1):
  if i>=L and i<=R:
    cnt +=1
    
print(cnt)
### BUGGY CODE ###

s = list(input())
l = len(s)
count = 0
while "ABC" in "".join(s):
	for i in range(l-2):
		if "".join(s[i:i+3]) == "ABC":
			s[i:i+3] = "BCA"
			count += 1
print(count)

### FIXED CODE ###

s = "Z".join(input().split("BC"))
l = len(s)
count = 0
cue = 0
for i in range(l):
	if s[i] == "A":
		cue += 1
	elif s[i] == "Z":
		count += cue
	else:
		cue = 0
print(count)
### BUGGY CODE ###

import math
n=int(input())
for i in range(1,n+1):
  s=0
  p=math.floor(math.sqrt(i))
  for x in range(1,p):
    for y in range(1,x+1):
      for z in range(1,y+1):
        if x**2+y**2+z**2+x*y+y*z+z*x==i:
          if x==y==z: s+=1
          elif x==y or y==z: s+=3
          else: s+=6          
  print(s)

### FIXED CODE ###

n=int(input())
dic={i:0 for i in range(1,n+1)}
for x in range(1,100):
  for y in range(1,x+1):
    for z in range(1,y+1):
      k=x**2+y**2+z**2+x*y+y*z+z*x
      if k<=n:
        if x==y==z: dic[k]+=1
        elif x==y or y==z: dic[k]+=3
        else: dic[k]+=6
for l in range(n):
  print(dic[l+1])
### BUGGY CODE ###

m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0]*(len(str2)+1)
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


### FIXED CODE ###

def LCS(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    LCS(str1,str2)
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
import collections
D=collections.defaultdict(int)
cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*10**keta)%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
S=input()
n=len(S)
D=[0]*2019
T=[0]*(n+1)
T[0]=1
for i in range(n):
  T[i+1]=(T[i]*10)%2019

cur=0
keta=0
ans=0
D[0]+=1
for s in S[::-1]:
  cur=(cur+int(s)*T[keta])%2019
  ans+=D[cur]
  D[cur]+=1
  keta+=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

import numpy as np

dp = [np.zeros(s+1) for _ in range(N)]


# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  dp[i] = np.mod((np.roll(dp[i-1], A[i]) + dp[i-1]*2), mod)
  temp_sum += A[i]

def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod

answer = int(answer)

print(answer)

### FIXED CODE ###

N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

dp = [[0]*(s+1) for _ in range(N)]
# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  for j in range(A[i]):
    dp[i][j] = (dp[i-1][j]*2) %mod
  for j in range(A[i], temp_sum+1):
    dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-A[i]]) %mod
  for j in range(temp_sum+1, temp_sum+1 + A[i]):
    dp[i][j] = (dp[i-1][j-A[i]]) %mod
  temp_sum += A[i]


def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod



print(answer)
### BUGGY CODE ###

import numpy as np

def test():
    n = int(input())
    a = np.array(list(map(int,input().split())))
    b = set(a)
    ans = 0
    for i in b:
        c = sum(a==i)
        if c > i:
            ans += c - i
        elif c < i:
            ans += c
    print(ans)


if __name__ == "__main__":
    test()


### FIXED CODE ###

import collections as coll

def test():
    n = int(input())
    a = list(map(int,input().split()))
    b = coll.Counter(a)
    ans = 0
    for i,j in b.items():
        if i < j:
            ans += j - i
        elif i > j:
            ans += j
    print(ans)


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

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=800
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)