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

n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,c+3):
  for j in range(1,n+2):
    for i in range(1,n+2):
      if i==1 and j==1 and k==1:
        continue
      if i+2*j+3*k>d+10:
        break
      dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=1
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]
for k in range(c+1):
  for j in range(n-k-a+1):
    for i in range(n-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+n)/(i+j+k)
print(dp[c][b][a])
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split(" ")))
m = Counter(A)
def nck(n, k): 
    C = [[0 for x in range(k+1)] for x in range(n+1)] 
  
    # Calculate value of Binomial Coefficient in bottom up manner 
    for i in range(n+1): 
        for j in range(min(i, k)+1): 
            # Base Cases 
            if j == 0 or j == i: 
                C[i][j] = 1
  
            # Calculate value using previously stored values 
            else: 
                C[i][j] = C[i-1][j-1] + C[i-1][j] 
  
    return C[n][k] 

choose = {n : nck(n, 2) for n in range(N//2)}
for i in range(len(A)):
    total =0
    m[A[i]] -= 1
    for key, value in m.items():
        # if key == A[i]:
        #     continue
        # else:
        if value in choose :
                total += choose[value]
        elif len(A) - value +1 in choose:
            total += choose[len(A) - value +1]
        else:
            newchoose = nck(value, 2)
            choose[value] = newchoose 
            total += newchoose
    m[A[i]] += 1
    # print(uniquethings*(uniquethings)//2)
    print(total)



### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split(" ")))
m = Counter(A)
def nck(n, k): 
    C = [[0 for x in range(k+1)] for x in range(n+1)] 
  
    # Calculate value of Binomial Coefficient in bottom up manner 
    for i in range(n+1): 
        for j in range(min(i, k)+1): 
            # Base Cases 
            if j == 0 or j == i: 
                C[i][j] = 1
  
            # Calculate value using previously stored values 
            else: 
                C[i][j] = C[i-1][j-1] + C[i-1][j] 
  
    return C

most_common,num_most_common = m.most_common(1)[0]
CHOOSE_MATRIX = nck(num_most_common, 2)
total = 0
for key, value in m.items():
        # if key == A[i]:
        #     continue
        # else:
    total += CHOOSE_MATRIX[value][2]


for i in range(len(A)):
    newtotal = total
    # m[A[i]] -= 1
    # for key, value in m.items():
    #     # if key == A[i]:
    #     #     continue
    #     # else:
    #     total += CHOOSE_MATRIX[value][2]
    # m[A[i]] += 1
    tosubtract = CHOOSE_MATRIX[m[A[i]]][2]
    newtotal -= tosubtract
    newtotal += CHOOSE_MATRIX[m[A[i]]- 1][2]
    print(newtotal)
    # print(uniquethings*(uniquethings)//2)
    # print(total)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [[0]*(h*w+1) for x in range(h*w+1)]

for key in p.keys():
    for i in range(key, h*w+1, d):
        if key == i:
            dp[key][i] = 0
        else:
            dp[key][i] = dp[key][i-d] + abs(p[i-d][0]-p[i][0]) + abs(p[i-d][1]-p[i][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[a][b]
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [0]*(h*w+1)
for i in range(h*w+1):
    if d < i:
        dp[i] = dp[i-d] + abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[b]-dp[a]
    print(ans)
### BUGGY CODE ###

from heapq import heapify,heapreplace
n,m = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(m)]

heapify(A)

BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
for b,c in BC:
    if c<A[0]:
        break
    for i in range(b):
        if A[0]>c:
            break
        heapreplace(A,c)
    
#print(A)
print(sum(A))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
r=[]
g=[]
b=[]
for i in range(n):
    tmp=s[i]
    if tmp=="R":
        r.append(i+1)
    elif tmp=="G":
        g.append(i+1)
    else:
        b.append(i+1)
for i in r:
    for j in g:
        for k in b:
            if (i<j and j<k):
                if j-i!=k-j:
                    ans+=1
            elif (i<k and k<j):
                if k-i!=j-k:
                    ans+=1
            elif (j<i and i<k):
                if i-j!=k-i:
                    ans+=1
            elif (j<k and k<i):
                if k-j!=i-k:
                    ans+=1
            elif (k<i and i<j):
                if i-k!=j-i:
                    ans+=1
            elif (k<j and j<i):
                if j-k!=i-j:
                    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
for i in range(n):
    for j in range(n):
        if i+j+j>=n:
            break
        s1=s[i]
        s2=s[i+j]
        s3=s[i+j*2]
        if s1!=s2 and s2!=s3 and s1!=s3:
            ans-=1
print(ans)
### BUGGY CODE ###

n = int(input())
list = list(map(int, input().split()))
ans = 1

for i in range(n):
    ans = ans * list[i]

if ans > 1000000000000000000:
    ans = -1
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        print(0)
        return

    ans = 1
    for item in A:
        ans = ans * item
        if ans > 1000000000000000000:
            print(-1)
            return

    print(ans)


main()
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
nums = []
for num in p:
    elm = (num * (num + 1) / 2) * (1 / num)
    nums.append(elm)
maxVal = 0
for i in range(n - k + 1):
    if sum(nums[i: i + k]) >= maxVal:
        maxVal = sum(nums[i: i + k])
    else:
        continue
print(maxVal)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
nums = []
elm = 0
for num in p:
    elm += (num * (num + 1) / 2) * (1 / num)
    nums.append(elm)
maxVal = nums[k-1]
for i in range(n - k):
    if nums[i + k] - nums[i] >= maxVal:
        maxVal = nums[i + k] - nums[i]
    else:
        continue
print(maxVal)
### BUGGY CODE ###

#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

found = False
for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        for k in range(n+1):
            if i + j + k > n:
                break
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
                found = True
                print("{} {} {}".format(i, j, k))
                break
        if found:
            break
    if found:
        break

if not found:
    print("-1 -1 -1")


### FIXED CODE ###

#!/usr/bin/env python

n, y = map(int, input().split())
# print(n, y)

found = False
for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        k = n - (i + j)
        if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n:
            found = True
            print("{} {} {}".format(i, j, k))
            break
    if found:
        break

if not found:
    print("-1 -1 -1")
### BUGGY CODE ###

n = int(input())
bricks = [int(a) for a in input().split()]

result = 0
numbers = []
for i in range(1, n + 1):
  try:
    number_index = bricks.index(i)
    numbers.append(i)
    result = result + number_index
    for j in range(number_index + 1):
      bricks.pop(0)
  except:
    if len(numbers) != 0:
      result = result + len(bricks)
    break

if len(numbers) == 0:
  print(-1)
else:
  print(result)

### FIXED CODE ###

import sys

n = int(input())
bricks = [int(a) for a in input().split()]

try:
  bricks.index(1)
except:
  print(-1)
  sys.exit()

result = 0
numbers = []
watch = 1
for i in range(n):
  if bricks[i] == watch:
    watch = watch + 1
  else:
    result = result + 1

print(result)
### BUGGY CODE ###

s = input()
ans = 0
for j in range(4, len(s)):
    for i in range(len(s) - j + 1):
        x = int(s[i:i + j])
        if x % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

S = input()
N = len(S)
SUM = [0] * (N + 1)
MOD = 2019

r = 1  # 10のi乗を2019で割った余り
S = S[::-1]
for i in range(N):
    A = r * int(S[i])
    SUM[i + 1] = (SUM[i] + A) % MOD
    r = r * 10 % MOD

cnt = [0] * 2019
ans = 0
for x in SUM:
    ans += cnt[x]
    cnt[x] += 1
print(ans)
### BUGGY CODE ###

aa=[]
a=int(input())
for i in range(0,a):
  aa.append(input().split(" "))

bb=[]
for j in range(0,a):
  bb.append(input().split(" "))
  
pattern=[]
zentai=[]
chouhuku=0

for m in range(0,a**a):
  for n in range(0,a):
    pattern.append(m//(a**n)%a)
  
  for w in range(0,a):
    if pattern.count(pattern[w])>=2:
      chouhuku=1
  
  if chouhuku==0:
    zentai.append(pattern)
  pattern=[]
  chouhuku=0


score=0
max=0

for ww in zentai:
  for z in range(0,a):
    if aa[z][0]<bb[int(ww[z])][0] and aa[z][1]<bb[int(ww[z])][1]:
      score=score+1

  if max<=score:
    max=score
  score=0

print(max)


### FIXED CODE ###

#解答確認後
n=int(input())
aa=[[int(i) for i in input().split()] for i in range(n)]
bb=[[int(i) for i in input().split()] for i in range(n)]

#print(aa)
#print(bb)

import operator
aa.sort(key=operator.itemgetter(1),reverse=True)
bb.sort()
  
#print(aa)
#print(bb)

answer=0
for b in bb:
  xb,yb=b
  for a in aa:
    xa,ya=a
    if xa<xb and ya<yb:
      answer=answer+1
      aa. remove (a)
      #print(aa)
      #print(bb)
      #print(answer)
      break
      
print(answer)
### BUGGY CODE ###

from collections import deque
def LI():
  return list(map(int,input().split()))

N,M,K = map(int,input().split())
A = LI()
B = LI()

res = 0
for i in range(N+1):
  for j in range(M+1):
    if sum(A[:i]) + sum(B[:j]) <= K:
      res = max(res, i+j)

print(res)


### FIXED CODE ###

import bisect
def LI():
  return list(map(int,input().split()))

N,M,K = map(int,input().split())
A = LI()
B = LI()

cumA = [0]
for a in A:
  cumA.append(cumA[-1]+a)

cumB = [0]
for b in B:
  cumB.append(cumB[-1]+b)

res = 0
for i in range(N+1):
  cuma = cumA[i]
  if cuma > K: continue
  rem = K-cuma
  deskb = bisect.bisect_right(cumB, rem)-1

  res = max(res, i+deskb)

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

n=int(input())
a=[int(input()) for i in range(n)]
b=a[:]
p=max(a)
b.remove(p)
q=max(b)

c=[i for i, x in enumerate(a) if x==p]

for i in range(n):
    if i not in c:
        print(p)
    else:
        print(q)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]

l1=sorted(a)[-1]
l2=sorted(a)[-2]

for i in a:
  if i==l1:
    print(l2)
  if i!=l1:
    print(l1)
### BUGGY CODE ###

C=[0]*(10**5+2)
C[0]=1
C[1]=1
S=[0]*(10**5+2)
t=1
while(t<=(10**5)):
    t+=1
    if(C[t]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k]=1

for i in range(1,(10**5),2):
    if(C[i]==0):
        if(C[(i+1)//2]==0):
            S[i]=1

N=int(input())
for i in range(N):
    l,r=map(int,input().split())
    c=0
    T=S[l:r+1]
    print(sum(T))


### FIXED CODE ###

C=[0]*(10**5+2)
C[0]=1
C[1]=1
s=[0]*(10**5+2)
S=[0]*(10**5+2)
t=1
while(t<=(10**5)):
    t+=1
    if(C[t]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k]=1

for i in range(1,(10**5),2):
    if(C[i]==0):
        if(C[(i+1)//2]==0):
            s[i]=1

for i in range(1,len(S)):
    S[i]+=s[i]+S[i-1]

N=int(input())
for i in range(N):
    l,r=map(int,input().split())
    print(S[r]-S[l-1])
### BUGGY CODE ###

import math

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

for i in range(M):
    A[-1] /= 2
    A.sort()

for j in range(N):
    A[j] = math.floor(A[j])

print(sum(A))

### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_minus = [-x for x in A]
heapify(A_minus)

for i in range(M):
    n = -heappop(A_minus) // 2
    heappush(A_minus, -n)

print(-sum(A_minus))
### BUGGY CODE ###

h,w=map(int,input().split())
a,s=[],[]
for i in range(h):
  t,tt=input(),[]
  for j in range(w):
    if t[j]=="#":a.append([i,j])
    tt.append(t[j])
  s.append(tt)
for f in range(1,2000):
  b=[]
  for k in a:
    i,j=k[0],k[1]
    if i!=0:
      if s[i-1][j]==".":s[i-1][j]=f;b.append([i-1,j])
    if i!=h-1:
      if s[i+1][j]==".":s[i+1][j]=f;b.append([i+1,j])
    if j!=0:
      if s[i][j-1]==".":s[i][j-1]=f;b.append([i,j-1])
    if j!=w-1:
      if s[i][j+1]==".":s[i][j+1]=f;b.append([i,j+1])
  if b==[]:print(f-1);break
  a=list(b)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  t=[]
  s=input()
  for j in range(w):
    if s[j]=="#":d.append((i,j));dc+=1;t.append(1)
    else:t.append(0)
  b.append(t)
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==0:b[x[0]+1][x[1]]=1;d.append((x[0]+1,x[1]));dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==0:b[x[0]-1][x[1]]=1;d.append((x[0]-1,x[1]));dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==0:b[x[0]][x[1]+1]=1;d.append((x[0],x[1]+1));dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==0:b[x[0]][x[1]-1]=1;d.append((x[0],x[1]-1));dc+=1
  count+=1
print(count-1)
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = deque([(0, 0, 0)])
    is_reachable = False
    while len(q) > 0:
        x, y, p = q.popleft()
        board[x][y] = p
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue
                if board[i][j] == WHITE:
                    q.append((i, j, p+1))
                    continue
                if board[i][j] > p+1:
                    q.append((i, j, p+1))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()


### FIXED CODE ###

import heapq
import sys

sys.setrecursionlimit(1000)

BLACK = '#'
WHITE = '.'


def m():
    H, W = [int(x) for x in input().split(' ')]
    board = [[c for c in list(input())] for _ in range(H)]

    # x, y, score
    q = [(0, 0, 0)]
    is_reachable = False
    while len(q) > 0:
        p, x, y = heapq.heappop(q)
        if x == H - 1 and y == W - 1:
            is_reachable = True

        nexts = [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]
        for i, j in nexts:
            if 0 <= i and i < H and 0 <= j and j < W:
                if board[i][j] == BLACK:
                    continue

                if board[i][j] == WHITE:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

                if board[i][j] > p+1:
                    board[i][j] = p+1
                    heapq.heappush(q, (p+1, i, j))
                    continue

    if is_reachable:
        blacks = 0
        for i in range(H):
            for j in range(W):
                if board[i][j] == BLACK:
                    blacks += 1
        ans = H*W - blacks - board[H-1][W-1] - 1
        print(ans)
    else:
        print(-1)


m()
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
cnt = [n-1]*n
for j in range(n**2):
    check = [1]*n
    flg = False
    flg2 = False
    for i in range(n):
        if cnt[i] == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        cnt[i] -= 1
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
            cnt[y-1] -= 1
        else:
            a[i].appendleft((x,y))
            cnt[i] += 1
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
for i in range(n):
    if cnt[i] != 0:
        print(-1)
        quit()
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.6:
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
    if not flg2:
        print(ans)
        quit()
### BUGGY CODE ###

class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): #S[l:r]indexでいうl文字目からr-1文字目
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
      
N =int(input())
S = str(input())

base1 = 1007
mod1 = 10**9+7

RH = RollingHash(S,base1,mod1)

#print(a,b)
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    low = 0
    high = min(j-i,N-j)+1
    while abs(low-high)>1:
      mid = (low+high)//2
      if RH.get(i,i+mid) != RH.get(j,j+mid):
        high = mid
      else:
        low = mid
    ans = max(ans,low)
    #print(i,j,low)
print(ans)      


### FIXED CODE ###

class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): #S[l:r]indexでいうl文字目からr-l文字目。r-l文字。
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    def check(self, d):
        ma = {}
        for i in range(N-d+1): #0からN-dまで
            p = self.get(i,i+d)
            if p in ma:
                if i - ma[p] >= d: #d文字以上離れているか
                  return True
            else:
                ma[p] = i
        return False
            
              
N =int(input())
S = str(input())

base1 = 1007
mod1 = 10**9+7

RH = RollingHash(S,base1,mod1)

left = 0
right = N//2+1
while right - left >1:
  mid = (left+right)//2
  if RH.check(mid): #こちらがokの方
    left = mid
  else:
    right = mid

print(left)
### BUGGY CODE ###

n,q=map(int,input().split())
s=list(input())
actable=[]
for i in range(len(s)-1):
    if s[i]=="A":
        if s[i+1]=="C":
            actable.append(i+1)
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in actable:
        if j>=l and j<=r-1:
            ans+=1
    print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
n,q=map(int,input().split())
s=list(input())
actable=[]
for i in range(len(s)-1):
    if s[i]=="A":
        if s[i+1]=="C":
            actable.append(i+1)
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    ans=bisect_left(actable,r)-bisect_left(actable,l)
    print(ans)
### BUGGY CODE ###

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

d=[[float("INF")]*n for i in range(n)]
for i in range(n):
  d[i][i]=0

for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=c
  d[b-1][a-1]=c
  
#ワーシャルフロイド法
#d[i][j]:iからjへの最短経路
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j],d[i][k]+d[k][j])

      
from itertools import permutations
per=list(permutations(r,R))

ans=float("INF")
for l in per:
  cnt=0
  for j in range(R-1):
    cnt+=d[l[j]-1][l[j+1]-1]
  ans=min(cnt,ans)
print(ans)

      
      
  


### FIXED CODE ###

n,m,R=list(map(int,input().split()))
r=list(map(int,input().split()))
dp=[[float("INF")]*n for i in range(n)]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  dp[a-1][b-1]=c
  dp[b-1][a-1]=c
for i in range(n):
  dp[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
from itertools import permutations
per=list(permutations(r,R))
ans=float("INF")
for tup in per:
  ans_kouho=0
  for i in range(R-1):
    ans_kouho=ans_kouho+dp[tup[i]-1][tup[i+1]-1]
  ans=min(ans,ans_kouho)
print(ans)
### BUGGY CODE ###

# C - Good Sequence
N = int(input())
a = list(map(int, input().split()))
count = 0

for i in range(N):
    if a[i] == a.count(a[i]):
        pass
    else:
        a[i] = ''
        count += 1

print(count)

### FIXED CODE ###

# C - Good Sequence
import collections
N = int(input())
a = list(map(int, input().split()))
count = 0

a_1 = collections.Counter(a)

for k,v in a_1.items():
    if k <= v:
        count += v-k
    else:
        count += v

print(count)