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

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q) > 0:
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    if now == T and step  == 0:  
        print(cnt//3)
        exit()
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
print(-1)
exit()



### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

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

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

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

L = int(input())
if L % 3 == 0:
  b = [i + 1 for i in range(L)]
  k = [(i * (L - i) * (L - i)) / 4 for i in b]
  print(max(k))
else: 
  import numpy as np
  b = np.arange(0.1, L+0.001, 0.001)
  k = [(i * (L - i) * (L - i)) / 4 for i in b]
  print(max(k))

### FIXED CODE ###

L = int(input())
if L % 3 == 0:
  b = [i + 1 for i in range(L)]
  k = [(i * (L - i) * (L - i)) / 4 for i in b]
  print(max(k))
else: 
  import numpy as np
  b = np.arange(0.1, L+0.005, 0.005)
  k = [(i * (L - i) * (L - i)) / 4 for i in b]
  print(max(k))
### BUGGY CODE ###

N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]

Mlst=set()

if N>=2:
    for s1 in range(N-1):
        for s2 in range(s1,N):
            x1,y1=XY[s1]
            x2,y2=XY[s2]
            x1,x2=min(x1,x2),max(x1,x2)
            y1,y2=min(y1,y2),max(y1,y2)
            if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                Mlst.add((y2-y1)*(x2-x1))
if N>=3:
    for s1 in range(N-2):
        for s2 in range(s1,N-1):
            for s3 in range(s2,N):
                x1,y1=XY[s1]
                x2,y2=XY[s2]
                x3,y3=XY[s3]
                x1,x2=min(x1,x2,x3),max(x1,x2,x3)
                y1,y2=min(y1,y2,y3),max(y1,y2,y3)
                if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                    Mlst.add((y2-y1)*(x2-x1))
if N>=4:
    for s1 in range(N-3):
        for s2 in range(s1,N-2):
            for s3 in range(s2,N-1):
                for s4 in range(s3,N):
                    x1,y1=XY[s1]
                    x2,y2=XY[s2]
                    x3,y3=XY[s3]
                    x4,y4=XY[s4]
                    x1,x2=min(x1,x2,x3,x4),max(x1,x2,x3,x4)
                    y1,y2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
                    if sum([x1<=X<=x2 and y1<=Y<=y2 for X,Y in XY])>=K:
                        Mlst.add((y2-y1)*(x2-x1))
print(min(Mlst))


### FIXED CODE ###

N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
XY=sorted(XY,key=lambda x:x[0])
Mlst=[]

if N>=2:
    for s1 in range(N-1):
        for s2 in range(s1+1,N):
            x1,y1=XY[s1]
            x2,y2=XY[s2]
            y1,y2=min(y1,y2),max(y1,y2)
            count=2
            for i in range(s1+1,s2):
                count+=y1<=XY[i][1]<=y2
            if count>=K:
                Mlst.append((y2-y1)*(x2-x1))
if N>=3:
    for s1 in range(N-2):
        for s2 in range(s1+1,N-1):
            for s3 in range(s2+1,N):
                x1,y1=XY[s1]
                x2,y2=XY[s2]
                x3,y3=XY[s3]
                x1,x2=x1,x3
                y1,y2=min(y1,y2,y3),max(y1,y2,y3)
                count=2
                for i in range(s1+1,s3):
                    count+=y1<=XY[i][1]<=y2
                if count>=K:
                    Mlst.append((y2-y1)*(x2-x1))
if N>=4:
    for s1 in range(N-3):
        for s2 in range(s1+1,N-2):
            for s3 in range(s2+1,N-1):
                for s4 in range(s3+1,N):
                    x1,y1=XY[s1]
                    x2,y2=XY[s2]
                    x3,y3=XY[s3]
                    x4,y4=XY[s4]
                    x1,x2=x1,x4
                    y1,y2=min(y1,y2,y3,y4),max(y1,y2,y3,y4)
                    count=2
                    for i in range(s1+1,s4):
                        count+=y1<=XY[i][1]<=y2
                    if count>=K:
                        Mlst.append((y2-y1)*(x2-x1))
print(min(Mlst))
### BUGGY CODE ###

def main():
    from collections import Counter
    N = int(input())
    X = [i for i in range(N + 1)]
    prime = [2, ]
    for i in range(3, N + 1):
        x = int(i ** 0.5) + 1
        for p in prime:
            if p > x:
                prime.append(i)
                break
            if i % p == 0:
                X[i] = p
                break
        else:
            prime.append(i)


    def cnt(n):
        L = list()
        while n != 1:
            L.append(X[n])
            n //= X[n]
        C = Counter(L)
        ans = 1
        for v in C.values():
            ans *= v + 1
        return ans


    A = 0

    for i in range(1, N + 1):
        A += cnt(i) * i

    print(A)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    x = n // 2
    for i in range(1, n + 1):
        m = n // i
        ans += i * ((m + 1) * m) // 2
    print(ans)


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

N = int(input())
L = [False for i in range(10**9+1)]
A = [int(input()) for n in range(N)]


for a in A:
    L[a] = not L[a]

print(sum(L))


### FIXED CODE ###

N = int(input())
A = [int(input()) for n in range(N)]
A = sorted(A)

res = []
tmp = A[0]
count = 1
for i in range(1,N):
    if A[i] == tmp:
        count += 1
    else:
        res.append(count%2 != 0)
        count = 1
    tmp = A[i]
res.append(count%2 != 0)

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

n,k = map(int,input().split())
p = list(map(int,input().split()))
max=0
sump=0
ans=0
for i in range(n-k+1):
    sump=sum(p[i:i+k])
    if sump>max:
        max=sump
ans=(max+k)/2
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
sump=sum(p[0:k])
max=sump
ans=0
for i in range(n-k):
    sump=sump-p[i]+p[i+k]
    if sump>max:
        max=sump
ans=(max+k)/2
print(ans)
### BUGGY CODE ###

import bisect

N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = accum[N] - accum[i]#(= sum(A[i:N]))
    index1l = bisect.bisect_left(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect_left(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], accum[i] - accum[index1], accum[index3] - accum[i], accum[N] - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
accum = [0 for i in range(N + 1)]
for i in range(N):
    accum[i + 1] = accum[i] + A[i]
total = accum[N]
#accum[i + 1] = A[0] + A[1] + ... + A[i]
#sum(A[i:j]) = A[i] + A[i+1] + ... + A[j-1] = accum[j] - accum[i]
ans = float('inf')
for i in range(2, N - 1, 1): #2番目の区切りを A[i-1]とA[i]の間に入れる
    zenhan = accum[i] #(= sum(A[:i]))
    kouhan = total - zenhan #(= accum[N] - accum[i] = sum(A[i:N]))
    index1l = bisect.bisect(accum, zenhan // 2, lo = 2, hi = i) - 1
    index1r = min(index1l + 1, i - 1)
    index3l = bisect.bisect(accum, zenhan + (kouhan // 2), lo = i + 2, hi = N) - 1
    index3r = min(index3l + 1, N - 1)
    for index1 in (index1l, index1r):
        for index3 in (index3l, index3r):
            B, C, D, E = accum[index1], zenhan - accum[index1], accum[index3] - zenhan, total - accum[index3]
            M = max(B, C, D, E)
            m = min(B, C, D, E)
            ans = min(ans, M - m)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())

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

C = list(set(A))

B = len(C) 

x = B - K

ans = 0

figure_list = [0] * B

if x<=0:
    print('0')
else:
    for i in range(B):
        stock = int(C[i])
        counter = 0
        for ii in range(N):
            if stock == A[ii]:
                counter += 1
        figure_list[i] = counter

    figure_list = sorted(figure_list)

    for i in range(B-K):
        ans += figure_list[i]

    print(ans)    

### FIXED CODE ###

N, K = map(int, input().split())

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

C = list(set(A))

B = len(C) 
x = B - K

d = {}

for i in A:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1

d = sorted(d.items(), key=lambda x:x[1])

ans = 0
count = 0

if x<=0:
    print('0')
else:
    for key, value in d:
        ans = ans + value
        count = count + 1
        if count == x:
            print(ans)
            break
### BUGGY CODE ###

# from numba import njit
 
N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

# @njit(cache=True)
def calc(N, M, A, X, Y):
    ans = 0
    for a in A:
        aa = (a // N + 1) * M + a % N + 1
        ans += X[aa]
        h = X[aa]
        if h < 0: continue
        Q = [(aa, h)]
        X[aa] -= 1
        Y[aa] = 0
        dd = (-1, 1, M, -M)
        while Q:
            i, h = Q.pop()
            for d in dd:
                j = i + d
                y = Y[j]
                if X[j] >= h + y:
                    X[j] -= 1
                    Q.append((j, h + y))
    return ans

print(calc(N, M, A, X, Y))

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

def calc(i0):
    h = X[i0]
    if h < 0: return
    Q = deque([(i0, h)])
    X[i0] -= 1
    Y[i0] = 0
    dd = (-1, 1, M, -M)
    while Q:
        i, h = deque.popleft(Q)
        for d in dd:
            j = i + d
            y = Y[j]
            if X[j] >= h + y:
                X[j] -= 1
                deque.append(Q, (j, h + y))
ans = 0
for a in A:
    aa = (a // N + 1) * M + a % N + 1
    ans += X[aa]
    calc(aa)
print(ans)
### BUGGY CODE ###

N=int(input())
a=[]
x=0
for i in range(N):

    h=list(input())

    h.sort(reverse=False)
    
    a.append(h)


while True:

    if len(a)==0:
        break
    
    x+=sum(range(a.count(a[0])))
    y=a[0]

    for j in range(a.count(y)):
        a.remove(y)
    

print(x)


### FIXED CODE ###

N=int(input())

H=[]
c=0
t=0
for i in range(N):
    h=list(input())
    h.sort(reverse=False)
    H.append(h)

H.sort(reverse=False)

for j in range(N-1):
    
    if H[j]==H[j+1]:
        c+=1

    else:
        t+=int((c)*(c+1)/2)
        c=0

if c:
    t+=int(((c)*(c+1)/2))
        

print(t)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
  query = input()
  if query == '1':
    s = s[::-1]
  else:
    t, f, c = query.split()
    if f == '1':
      s = c + s
    else:
      s = s + c
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
cnt = 0
for i in range(q):
  query = input()
  if query == '1':
    cnt += 1
  else:
    t, f, c = query.split()
    if (f == '1' and cnt % 2 == 0) or (f == '2' and cnt % 2 == 1):
      s.appendleft(c)
    else:
      s.append(c)
if cnt % 2 == 0:
  print(''.join(s))
else:
  s.reverse()
  print(''.join(s))
### BUGGY CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
Fs = list(map(int, input().split()))

As.sort()
Fs.sort(reverse=True)
maxAF = max([A*F for A, F in zip(As, Fs)])

def isOK(X):
    rest = K
    for A, F in zip(As, Fs):
        if A*F > X:
            A2 = X//F
            d = A-A2
            if d > rest:
                return False
            rest -= d
    return True

ng, ok = -1, maxAF
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

N, K = map(int, input().split())
As = list(map(int, input().split()))
Fs = list(map(int, input().split()))

As.sort()
Fs.sort(reverse=True)
maxAF = max([A*F for A, F in zip(As, Fs)])

def isOK(X):
    rest = K
    for A, F in zip(As, Fs):
        if A*F > X:
            A2 = X//F
            d = A-A2
            if d > rest:
                return False
            rest -= d
    return True

ng, ok = -1, maxAF
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import collections
n = int(input())
a = [int(i) for i in input().split()]
cola = collections.Counter(a)
mult = [1] * (10**6+1)
seta = set(a)

for s in seta:
  tmp = s * 2
  while tmp <= 10 ** 6:
    mult[tmp] = 0
    tmp += s
  
ans = 0
for s in seta:
  if cola[s] == 1 and mult[s] == 1:
    ans += 1
    
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
m = [True] * (10**6+1)
s = list(set(a))
for u in s:
    t = u * 2
    while t <= 10 ** 6:
        m[t] = False
        t += u
r = 0
for u in s:
    if c[u] == 1 and m[u] == True:
        r += 1
print(r)
### BUGGY CODE ###

n = int( raw_input( ) )
eles = []
for i in range( n ):
	op = raw_input( ).split( " " )
	if "insert" == op[0]:
		eles.insert( 0, op[1] )
	elif "delete" == op[0]:
		for i, val in enumerate( eles ):
			if op[1] == val:
				eles.pop( i )
				break
	elif "deleteFirst" == op[0] :
		del eles[0]
	elif "deleteLast" == op[0]:
		eles.pop( )

print( " ".join( eles ) )

### FIXED CODE ###

import sys
from collections import deque

n = int( sys.stdin.readline( ) )
que = deque( )
lines = sys.stdin.readlines()
for line in lines:
	op = line.rstrip().split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )


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

#2
n = int(input())
a = 0
for i in range(1, n+1):
    if i**2 <= n:
        a = i**2
    else: continue
print(a)

### FIXED CODE ###

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

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

count = 0

for a_idx in range(len(length_list) - 2):
    for b_idx in range(a_idx+1, len(length_list) - 1):
        for c_idx in range(b_idx+1, len(length_list)):
            a = length_list[a_idx]
            b = length_list[b_idx]
            c = length_list[c_idx]
            # print(a,b,c)
            if a < b+c and b < c+a and c < a+b:
                count += 1  

print(count)

### FIXED CODE ###

from bisect import bisect_left

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

count = 0
length_list.sort()

for a_idx in range(n - 2):
    for b_idx in range(a_idx + 1, n - 1):
        a = length_list[a_idx]
        b = length_list[b_idx]

        left_count = bisect_left(length_list, a+b)
        count += max(0, left_count - b_idx - 1)


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

N=int(input())
total=1
A=list(map(int,input().split()))
for i in range(N):
  total*=A[i]
  
if 1*(10**18)+1<=total:
  print("-1")
else:
  print(total)

### FIXED CODE ###

N=int(input())
total=1
A=list(map(int,input().split()))
flag=True
high=1*(10**18)+1
if A.count(0)>=1:
  total=0
else:
  for i in range(N):
    total*=A[i]
    if high<=total:
      flag=False
      break

if not flag:
  print("-1")
else:
  print(total)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    i = 1
    while i < n:
        j = i-1
        while -1 < j:
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
            else:
                dp[j] = 0
            j -= 1
        i += 1
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

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

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])


### FIXED CODE ###

# スペース区切りの整数入力
h,n = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

#下から順に最小の積み上げを作る
bsum=[0]
for i in range(1,h+1):
    min_bsum = 9999999999999
    for atk in range(n):
        if bsum[max(0,i-a[atk])]+b[atk] < min_bsum:
            min_bsum = bsum[max(0,i-a[atk])]+b[atk]
    bsum.append(min_bsum)

#指定のHのコストを表示
print(bsum[h])
### BUGGY CODE ###

R,C,K = map(int,input().split())
V = [[0 for c in range(C+1)] for r in range(R+1)]
for i in range(K):
	r,c,v = map(int,input().split())
	V[r][c] = v
dp = [[[0 for i in range(4)] for j in range(C+1)] for k in range(R+1)]
for r in range(1, R+1):
	for c in range(1, C+1):
		v = V[r][c]
		under_val = max(dp[r-1][c])
		dp[r][c][0] = max(under_val, dp[r][c-1][0])
		dp[r][c][1] = max(under_val + v, dp[r][c-1][0] + v, dp[r][c-1][1])
		dp[r][c][2] = max(dp[r][c-1][1] + v, dp[r][c-1][2])
		dp[r][c][3] = max(dp[r][c-1][2] + v, dp[r][c-1][3])
print(max(dp[-1][-1]))

### FIXED CODE ###

R,C,K = map(int,input().split())
V = [[0 for c in range(C+1)] for r in range(R+1)]
for i in range(K):
	r,c,v = map(int,input().split())
	V[r][c] = v

dp = [[0 for i in range(4)] for j in range(C+1)]
for r in range(1, R+1):
	for c in range(1, C+1):
		v = V[r][c]
		under_val = max(dp[c])
		dp[c][0] = max(under_val, dp[c-1][0])
		if v > 0:
			dp[c][1] = max(under_val + v, dp[c-1][0] + v, dp[c-1][1])
			dp[c][2] = max(dp[c-1][1] + v, dp[c-1][2])
			dp[c][3] = max(dp[c-1][2] + v, dp[c-1][3])
		else:
			dp[c][1] = dp[c-1][1]
			dp[c][2] = dp[c-1][2]
			dp[c][3] = dp[c-1][3]
print(max(dp[-1]))
### BUGGY CODE ###

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

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
    #heapq.heappush(a, -2)
import copy
for unko in range(k):

    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    ans=[0]*n
    #print("start",a)
    for i,aa in  enumerate(a):
        if cnt==0:
            ans[i]+=1
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        else:
            while 1:
                tmp=heapq.heappop(denkyu)
                if i<tmp:
                    heapq.heappush(denkyu, tmp)
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break
            
            ans[i]+=cnt+1
            
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        #print(aa,denkyu)
    #print(unko,ans,a)


    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    for ii in  range(n):
        
        i=n-ii-1
        if cnt==0:
            if a[i]>0:
                cnt+=1
                heapq.heappush(denkyu,-1*(i-a[i]-1))
        else:
            while 1:
                tmp=heapq.heappop(denkyu)*(-1)
                if i>tmp:
                    heapq.heappush(denkyu, tmp*(-1))
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break
  
            ans[i]+=cnt
            if a[i]>0:
                cnt+=1
                heapq.heappush(denkyu,(i-a[i]-1)*(-1))
        #print("migi",a[i],denkyu)

    a = copy.deepcopy(ans)
    if min(a)==n:
        break
    #print(unko,a)


print(" ".join(list(map(str,a))))

### FIXED CODE ###

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

for _ in range(k):
    imos=[0]*(n+1)
    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,1+i+a[i])]-=1
    
    a[0]=imos[0]
    if a[0]==n:
        flag=0
    else:
        flag=1

    for i in range(1,n):
        a[i]=a[i-1]+imos[i]
        if a[i]!=n:
            flag=1
    
    if flag==0:
        break

print(" ".join(list(map(str,a))))
### BUGGY CODE ###

n = int(input())
S = [int(_) for _ in input().split()]
q = int(input())
T = [int(_) for _ in input().split()]
cnt = 0

# from copy import deepcopy

# for t in T:
#     S_ = deepcopy(S)

#     while S_:
#         ind = len(S_) // 2

#         if t == S_[ind]:
#             cnt += 1
#             break
#         elif t < S_[ind]:
#             S_ = S_[:ind]
#         else:
#             S_ = S_[ind + 1:]


def binary_search(ary, target):

    if ary:
        ind = len(ary) // 2
        if target == ary[ind]:
            return True
        elif target < ary[ind]:
            return binary_search(ary[:ind], target)
        else:
            return binary_search(ary[ind + 1:], target)

    else:
        return False


for target in T:
    if binary_search(S, target):
        cnt += 1

if __name__ == '__main__':
    print(cnt)



### FIXED CODE ###

# def binary_search_original(ary, target):

#     if ary:
#         ind = len(ary) // 2
#         if target == ary[ind]:
#             return True
#         elif target < ary[ind]:
#             return binary_search(ary[:ind], target)
#         else:
#             return binary_search(ary[ind + 1:], target)

#     else:
#         return False


def binary_search(ary, target):

    left = 0
    right = len(ary)

    while left < right:
        mid = (left + right) // 2

        if ary[mid] == target:
            return True
        elif ary[mid] < target:
            left = mid + 1
        else:
            right = mid

    return False


if __name__ == '__main__':

    n = int(input())
    S = [int(_) for _ in input().split()]
    q = int(input())
    T = [int(_) for _ in input().split()]
    cnt = 0

    for target in T:
        if binary_search(S, target):
            cnt += 1

    print(cnt)