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

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return left


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == -1:
        #last.insert(0, val)
        last = [val] + last
    else:
        last[temp] = val
    #print(last)
print(len(last))




### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] < threshold:
            right = mid
        else:
            left = mid
    return right


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == len(last):
        #last.insert(0, val)
        last.append(val)
    else:
        last[temp] = val
    #print(last)
print(len(last))
### BUGGY CODE ###

A,B,K = [int(x) for x in input().split()]
for i in range(A,B+1):
  if(i<= A+K-1 or i>= B-K+1):
    print(i)
    

### FIXED CODE ###

A,B,K = [int(x) for x in input().split()]
if(B-A+1>2*K):
  for i in range(A,A+K):
    print(i)
  for i in range(B-K+1,B+1):
    print(i)
else:
  for i in range(A,B+1):
    if(i<= A+K-1 or i>= B-K+1):
      print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[]
for i in range(m):
    b,c = map(int, input().split(" "))
    bc = bc + [c]*b
bc.sort(reverse=True)
for i in range(n):
    if len(bc) <= i or bc[i] <= a[i]:
        break
    a[i] = bc[i]
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

#Frog2
n,k=map(int,input().split())
h=list(map(int,input().split()))
h.insert(0,0)
dp={1:0}
for val3 in range(2,n+1):
    dp[val3]=int(1e9+9)
for val in range(2,n+1):
    for val2 in range(1,min(val,k+1)):
        dp[val]=min(dp[val],dp[val-val2]+abs(h[val]-h[val-val2]))
print(dp[n])
        

### FIXED CODE ###

#Frog2
n,k=map(int,input().split())
h=list(map(int,input().split()))
h.insert(0,0)
dp={1.0:0}
for val3 in range(2,n+1):
    dp[val3]=float(1e9)
for val in range(2,n+1):
    for val2 in range(1,min(val,k+1)):
        dp[val]=min(dp[val],dp[val-val2]+abs(h[int(val)]-h[int(val-val2)]))
print(dp[n])
### BUGGY CODE ###

N,W = map(int, input().split())
item = []
for i in range(N):
	item.append(list(map(int, input().split())))
item = [[0,0]] + item

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
	for j in range(1,W+1):
		v = item[i][1]
		w = item[i][0]
		if w>j:
			dp[i][j] = dp[i-1][j]
		else:
			dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(dp[N][W])

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])

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

import math
import copy
H,N=map(int,input().split())

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        ndp[j]=min(ndp[j-A]+B,dp[j])

    for j in range(max(H-A+1,0),H+1):
        if ndp[j]==None:
            continue

        if ndp[-1]!=None:
            ndp[-1]=min(ndp[j]+B,ndp[-1])
        else:
            ndp[-1]=ndp[j]+B
    
    if A >= H and dp[-1]!=None:
        ndp[-1]=min(B,dp[-1])

    dp=ndp

print(dp[-1])

### FIXED CODE ###

import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = []
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

dp = [1]
if 1 not in a:
    dp.append(1)
else:
    dp.append(0)

for i in range(2, N + 1):
    if i not in a:
        tmp = dp[0] + dp[1]
    else:
        tmp = 0
    dp[0] = dp[1]
    dp[1] = tmp

print(dp[-1] % mod)

### FIXED CODE ###

import collections
mod = 10 ** 9 + 7
N, M = map(int, input().split())
a = collections.deque([])
for _ in range(M):
    a_m = int(input())
    if len(a) > 0 and a_m == a[-1] + 1:
        print(0)
        exit()
    a.append(a_m)

dp = [1]

if len(a) > 0:
    if 1 != a[0]:
        dp.append(1)
    else:
        dp.append(0)
        a.popleft()
else:
    dp.append(1)

for i in range(2, N + 1):
    if len(a) > 0:
        if i != a[0]:
            tmp = dp[0] + dp[1]
        else:
            tmp = 0
            a.popleft()
    else:
        tmp = dp[0] + dp[1]
    dp[0] = dp[1]
    dp[1] = tmp

print(dp[-1] % mod)
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations
 
 
def p_e():
    N = int(input())
    S = input()
 
    S_idx = defaultdict(list)
 
    for i in range(N):
        S_idx[S[i]].append(i)
 
    max_ans = 0
    for c in S_idx.keys():
        if len(S_idx[c]) <= 1:
            continue
 
        comb_list = list(combinations(S_idx[c], 2))
        i = 1
 
        f = True
        while f:
            i += 1
            f = False
            for comb in comb_list:
                a = comb[0]
                b = comb[1]
                if a + i - 1 >= N or b + i - 1 >= N:
                    comb_list.remove(comb)
                    continue
 
                if a + i - 1 >= b:
                    comb_list.remove(comb)
                    continue
 
                if S[a + i - 1] == S[b + i - 1]:
                    f = True
                else:
                    comb_list.remove(comb)
 
        if max_ans < i - 1:
            max_ans = i - 1
 
    print(max_ans)
 
 
if __name__ == '__main__':
    p_e()

### FIXED CODE ###

def p_e():
    N = int(input())
    S = input()

    l, r, ans = 0, 0, 0

    while r < N:
        if S[l:r] in S[r:N]:
            ans = max(ans, r - l)
            r += 1
        else:
            l += 1

    print(ans)


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

N = int(input())

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

for i in range(1,N+1):
    #print(i)
    print(A.index(i)+1, end=" ")

### FIXED CODE ###

N = int(input())

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

ans = [0]*N
for i,j in enumerate(A):
    ans[j-1]=i+1
print(*ans)
### BUGGY CODE ###

S = input()
counter = {0: 1}
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    mod = num % 2019
    if mod in counter:
        counter[mod] += 1
    else:
        counter[mod] = 1
    ten *= 10

ret = 0
for v in counter.values():
    ret += v * (v - 1) // 2
print(ret)

### FIXED CODE ###

from collections import Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

counter = Counter(mods)
ret = 0
for v in counter.values():
    ret += v * (v - 1) // 2
print(ret)
### BUGGY CODE ###

N = int(input())
S = list(input())
index = [i for i in range(N)]

ans = 0

from itertools import permutations, combinations,combinations_with_replacement,product,chain, zip_longest

it = zip_longest(index, S)

C = list(combinations(it,3))

i = 0

for c in C:
    i, j, k = c[0][0]+1, c[1][0]+1, c[2][0]+1
    c1, c2, c3 = c[0][1], c[1][1], c[2][1]

    if i < j < k:
        if c1 != c2 and c1 != c3 and c2 != c3:
            if j-i != k-j:
                ans += 1

print(ans)


### FIXED CODE ###

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

cntOne = S.count('R') * S.count('G') * S.count('B')
cntTwo = 0


for i in range(N-1):
    for j in range(i+1, N):
        k = (j - i) + j
        if k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                cntTwo += 1
print(cntOne - cntTwo)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, X, Y = map(int, readline().split())

answer = [0 for _ in range(0, N)]
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i - j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
for a in answer[1:]:
    print(a)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, X, Y = map(int, readline().split())

answer = [0 for _ in range(0, N)]
for i in range(1, N+1):
    for j in range(i, N+1):
        distance1 = abs(i-j)
        distance2 = abs(X-i) + abs(Y-j) + 1
        distance3 = abs(X-j) + abs(Y-i) + 1
        min_distance = min(distance1, distance2, distance3)
        answer[min_distance] += 1
for i, a in enumerate(answer):
    if i != 0:
        print(a)
### BUGGY CODE ###

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

A = A + [0]
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()

print(*S)

### FIXED CODE ###

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

A = A + [0]
K = min(K, 50)
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
print(*S)
### BUGGY CODE ###

L=input()
n=len(L)
mod=10**9+7
table=[None]*n
table[0]=1
for i in range(1,n):
    table[i]=3*table[i-1]%mod
ans=0
k=1
for i in range(n):
    if L[i]=="1":
        ans=(ans+k*table[n-i-1])%mod
        k*=2
ans+=k    
print(ans%mod)

### FIXED CODE ###

L=list(map(int,list(input())))
n=len(L)
mod=10**9+7
table=[None]*n
table[0]=1
for i in range(1,n):
    table[i]=3*table[i-1]%mod
ans=0
k=1
for i in range(n):
    if L[i]==1:
        ans=(ans+k*table[n-i-1])%mod
        k=k*2%mod
ans+=k    
print(ans%mod)
### BUGGY CODE ###

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

ans = 0

for i in range(N):
	ans = (ans +  A[i] * sum(A[i+1:N])) % (10**9+7)

print(ans)

### FIXED CODE ###

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

DIV = 10**9+7
ans = 0
Asum = sum(A)
Asum_sq = Asum**2

for i in range(N):
	ans += A[i]**2

res = (Asum_sq-ans)//2
print(res%DIV)
### BUGGY CODE ###

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

D=[0]*100
C=0
W=[0]*10
R=len(set(S))**3
u=0
for i in range(N-2):
    if(C==R):
        break
    if(W[int(S[i])]<10):
        u=len(set(S[i+1:N]))
        for j in range(i+1,N-1):
            if(W[int(S[i])]==u):
                break
            s=str(S[i])+str(S[j])
            if(D[int(s)]==0):
                D[int(s)]=1
                W[int(S[i])]+=1
                C+=len(set(S[j+1:N]))
print(C)



### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for a in range(10):
  for b in range(10):
    for c in range(10):
      a, b, c = str(a), str(b), str(c)
      a_find = s.find(a)
      if a_find == -1:
        continue
      b_find = s.find(b, a_find + 1)
      if b_find == -1:
        continue
      c_find = s.find(c, b_find + 1)
      if c_find == -1:
        continue
      ans += 1
print(ans)
### BUGGY CODE ###

import math
data = 1000000000000
N = int(input())
for i in range(int(math.sqrt(N))+1):
    for j in range(N+1):
        if i*j == N:
            if data >i+j-2:
                data = i+j-2

print(data)

### FIXED CODE ###

import math
data = 1000000000000
N = int(input())
for i in range(1,int(math.sqrt(N))+1):
    j = N/i
    if j-int(j) == 0:
        if data >i+int(j)-2:
            data = i+int(j)-2

print(data)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
big = max(A)
for i in range(N):
  if A[i] != big: print(big)
  else: print(max(A[:i] + A[i + 1:])) 

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
big = max(A)
place = A.index(big)
for i in range(N):
  if i != place: print(big)
  else: print(max(A[:i] + A[i + 1:]))
### BUGGY CODE ###

n = int(input())
l = list(input())
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    flag = True
    if l[i] == l[j]:
      flag = False
    for k in range(j+1,n):
      if l[j] != l[k] and l[i] != l[k] and j-i != k-j and flag:
        count += 1
print(count)

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
s = list(input())

c  = Counter(s)  

num = c['R']*c['G']*c['B']

for j in range(n):
    for d in range(1,min(j,n-j-1)+1):
        i = j-d
        k = j+d
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            num -= 1
print(num)
### BUGGY CODE ###

import numpy as np
A,B,N=map(int,input().split())
if(N<=B):
    x = np.array([j for j in range(N+1)])
else:
    x = np.array([j for j in range(B+1)])    
val=np.floor(A*x/B)-A*np.floor(x/B)
print(int(np.max(val)))

### FIXED CODE ###

import math
A,B,N=map(int,input().split())
if(N<B):
    x = N
else:
    x =B-1    

print(int( math.floor(A*x/B)-A*math.floor(x/B)  ))
### BUGGY CODE ###

N = int(input())
ARR = list(map(int,input().split()))
def calculate(n, arr):
    result = 0
    for left in range(0, n):
        right = left
        sum = arr[left]
        while right+1 < n:
            if sum ^ arr[right+1] == (sum + arr[right+1]):
                result = result + 1
                right = right + 1
                sum = sum + arr[right]
            else:
                break
        sum = sum + right - left
    print(result + n)

calculate(N, ARR)


### FIXED CODE ###

N = int(input())
ARR = list(map(int,input().split()))
def calculate(n, arr):
    result = 0
    right = 0
    sum = arr[0]
    for left in range(0, n):
        while right+1 < n:
            if sum ^ arr[right+1] == (sum + arr[right+1]):
                right = right + 1
                sum = sum + arr[right]
            else:
                break
        result = result + right - left + 1
        sum = sum - arr[left]
    print(result)

calculate(N, ARR)
### BUGGY CODE ###

N, K, C = list(map(int, input().split(" ")))
S = input()
S_list = [i for i in S]

F_list = []
B_list = []
count = 0
len_S = len(S_list)
for j in range(K):
    for i in range(count, len_S):
        if S_list[i] == "o":
            F_list.append(i+1)
            count += C+1
            break
        else:
            count += 1

#S_list = S_list[::-1]

count = 0
for j in range(K):
    for i in range(count, len_S):
        if S_list[-(i+1)] == "o":
            B_list.append(len_S-i)
            count += C+1
            break
        else:
            count += 1

for i in F_list:
    if i in B_list:
        print(i)

### FIXED CODE ###

N, K, C = list(map(int, input().split(" ")))
S = input()

F_list = []
B_list = []

f_count = 0
b_count = 0
f_rest = 0
b_rest = 0
S_len = len(S)
# o
for i in range(S_len):
    if f_count == K and b_count == K:
        break

    if f_count < K:
        if S[i] == "o" and f_rest == 0:
            f_rest += C
            f_count += 1
            F_list.append(i+1)
        else:
            if f_rest > 0:
                f_rest -= 1
    if b_count < K:
        if S[-(i+1)] == "o" and b_rest == 0:
            b_rest += C
            b_count += 1
            B_list.append(S_len-i)
        else:
            if b_rest > 0:
                b_rest -= 1

for i in range(K):
    if F_list[i] == B_list[-(i+1)]:
        print(F_list[i])
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype='int32')
for i in range(m):
    idx = a.argmax()
    a[idx] = a[idx] // 2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp = (heapq.heappop(a) * (-1)) // 2
    heapq.heappush(a, -tmp)
print(sum(a) * -1)
### BUGGY CODE ###

import math

N = int(input())
S = input()
mod = 10**9 + 7

left = 0
ret = 1
for i in range(len(S)):
    if S[i] == 'W':
        if left % 2 == 1:
            left += 1
        else:
            if left > 0:
                ret *= left
                left -= 1
            else:
                print(0)
                exit()
    else:
        if left % 2 == 1:
            ret *= left
            left -= 1
        else:
            left += 1

if left > 0:
    print(0)
    exit()
            
for i in range(1, N+1):
    ret *= i
    ret %= mod
print(ret)


### FIXED CODE ###

import math

N = int(input())
S = input()
mod = 10**9 + 7

left = 0
ret = 1
for i in range(len(S)):
    if S[i] == 'W':
        if left % 2 == 1:
            left += 1
        else:
            if left > 0:
                ret *= left
                ret %= mod
                left -= 1
            else:
                print(0)
                exit()
    else:
        if left % 2 == 1:
            ret *= left
            ret %= mod
            left -= 1
        else:
            left += 1

if left > 0:
    print(0)
    exit()
            
for i in range(1, N+1):
    ret *= i
    ret %= mod
print(ret)
### BUGGY CODE ###

N, Y = map(int, input().split())
x = 0
y = 0
z = 0

if Y/1000 - N < 0:
    print(-1,-1,-1)

else:
    for x in range(0, int(Y - 1000 * N / 9000)+ 1):
        y = (Y - 1000 * N - 9000 * x) / 4000
        if y == int(y)  and y >= 0:
            y = int(y)
            z = N - x - y
            if 0 <= z <= N:
                print(x, y, z)
                break
        if x == int(Y - 1000 * N / 9000):
            print(-1, -1, -1)
            break

### FIXED CODE ###

N, Y = map(int, input().split())
x,y,z = 0,0,0
for x in range(0, N + 1):
    for y in range(0, N - x +1):
        z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y:
            break
    if 10000 * x + 5000 * y + 1000 * z == Y :
        break

if 10000 * x + 5000 * y + 1000 * z == Y :
    print(x,y,z)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
x = a.pop(-1)
kj = [1,1]
for i in range(2,x+1):
  kj.append(kj[-1]*i)
ans_val = []
ans_list = []
for i in a:
  ans_val.append(kj[x]/(kj[x-i]*kj[i]))
  ans_list.append(i)
print(x,ans_list[ans_val.index(max(ans_val))])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
x = a.pop(-1)
x2 = x/2
ans = a[0]
t = abs(x2-ans)
for i in a:
  if abs(x2-i) < t:
    ans = i
    t = abs(x2-ans)
print(x,ans)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = ((1,0),(-1,0),(0,1),(0,-1))

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and visited[_h][_w] == 0 and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

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

s = (1000, 0, 0)
mmax = 1000

q = []
q.append(s)
while len(q) > 0:
    m,k,d = q.pop()
    if d == N-1:
        m += k*A[d]
        if mmax < m:
            mmax = m
    else:
        q.append((m,k,d+1))
        if m > A[d]:
            x = m // A[d]
            nm = m-x*A[d]
            nk = k+x
            q.append((nm,nk,d+1))
        if k > 0:
            nm = m+k*A[d]
            q.append((nm, 0, d+1))
            x = nm // A[d]
            if x > 0:
                q.append((nm - x*A[d], x, d+1))
print(mmax)  


### FIXED CODE ###

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

m = 1000
k = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        m += k * A[i]
        k = 0
    elif A[i] < A[i+1]:
        m += k * A[i]
        k = m // A[i]
        m -= k * A[i]
    else:
        pass
m += (k * A[-1])
print(m)
### BUGGY CODE ###

#import numpy as np
from operator import add
import sys
def calc_double(n,i):
    return float(n/i)

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N=listA[0]
lis_0=[0]*N[0]
lis=listA[1]
for idx1,i in enumerate(lis):
    lis_=[]
    for val in lis:
      lis_.append(calc_double(val,i))
    for idx,num in enumerate(lis_):
        if idx!=idx1:
            if num.is_integer(): lis_[idx]=1
            else: lis_[idx]=0
        else:lis_[idx]=0
    lis_0 = list(map(add, lis_, lis_0))
        
print(lis_0.count(0))

### FIXED CODE ###

## 動画見てアルゴリズムを知った
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;

lis=listA[1]
m=max(lis)
lis0=[0]*(m+1)
for i in lis:
    if lis0[i]!=2: 
        j=1
        while i*j<=m:
            lis0[i*j]+=1
            j+=1
            
count=0
for i in lis:
    if lis0[i]==1: count+=1
print(count)