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

import sys
input = sys.stdin.readline
from itertools import combinations

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=1<<60

for rail in range(N-1):
    I=combinations(list(range(N)),rail)

    for rails in I:
        #print(rails)
        if ANS==0:
            break

        for i in range(1<<rail):
            X=[0]
            Y=[0]
            for j in range(rail):
                if (1<<j) & i ==0:
                    X.append(P[rails[j]][0])
                else:
                    Y.append(P[rails[j]][1])

            C=0
            for x,y,p in P:
                MIN=1<<30
                for xx in X:
                    MIN=min(abs(xx-x),MIN)
                for yy in Y:
                    MIN=min(abs(yy-y),MIN)

                C+=MIN*p
                if C>=ANS:
                    break

            #print(X,Y,C)

            ANS=min(ANS,C)

    print(ANS)

ANS=1<<60
for x,y,c in P:
    ANS=min(ANS,abs(x)*c,abs(y)*c)
    for xx,yy,cc in P:
        if x==xx and y==yy:
            continue
        ANS=min(ANS,abs(x-xx)*c,abs(y-yy)*c)

print(ANS)
print(0)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
P=[list(map(int,input().split())) for i in range(N)]
ANS=[1<<60]*(N+1)
ANS[-1]=0

DP1=[20000]*N

S=0
for i in range(N):
    x,y,p=P[i]
    DP1[i]=min(abs(x),abs(y))
    S+=DP1[i]*p

ANS[0]=S

def dfs(DP,now,used):
    if used==N-1:
        return
    for next_town in range(now,N):
        x,y,p=P[next_town]

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][0]-x))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

        DP2=list(DP)
        S=0
        for i in range(N):
            DP2[i]=min(DP2[i],abs(P[i][1]-y))
            S+=DP2[i]*P[i][2]

        #print(DP,now,used,next_town,DP2)
            
        ANS[used+1]=min(ANS[used+1],S)
        if S!=0:
            dfs(DP2,next_town+1,used+1)

dfs(DP1,0,0)

for i in range(1,N):
    ANS[i]=min(ANS[i],ANS[i-1])

print(*ANS)
### BUGGY CODE ###

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

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    #ans = ans + (lcm // v)
    ans = (ans + (lcm // v)) % MOD
print(ans % MOD)


### FIXED CODE ###

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

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)
### BUGGY CODE ###

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

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求める
AX = [A[i]^A[i-1] for i in range(N)]
BX = [B[i]^B[i-1] for i in range(N)]

ans = []
for k in range(N):
    AX2 = AX[k:N]
    AX2.extend(AX[0:k])
    if AX2 == BX:
        # kに対応するxを求める
        x = A[k]^B[0]
        print(k, x)


### FIXED CODE ###

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

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求め,kからxを求める
AX = [A[i]^A[i-1] for i in range(N)]
AX += AX
BX = [B[i]^B[i-1] for i in range(N)]

#print(AX)
#print(BX)

# BXの頭と終わりが同じ数字の並びの場合、その数mを求める
m = 0
for i in range(1, N):
    if BX[m] == BX[i]:
        m += 1
    else:
        m = 0
#print(m)

i, j, k = 0, 0, 0
while k < N:
    while True:
        #print("i,j: {},{},{}".format(i,j,k))
        if AX[i] == BX[j]:
            if j == N-1:
                print(k, A[k]^B[0])
                i += 1
                j = m
                break
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:
            i += 1
            break
    
    k = i-j
### BUGGY CODE ###

import itertools
 
S = list(map(int, input().strip().split()))
N = S[0]
K = S[1]
p = list(map(int, input().strip().split()))
lists = []
for l in itertools.combinations(p, K):
  sums = sum(list(l))
  lists.append(sums)
 
print(min(lists))


### FIXED CODE ###

S = list(map(int, input().strip().split()))
N = S[0]
K = S[1]
p = list(map(int, input().strip().split()))
lists = []
for l in range(K):
  lists.append(min(p))
  p.remove(min(p))
  
print(sum(lists))
### BUGGY CODE ###

s = input()
q = int(input())

cnt = 0
for i in range(q):
    q_very = input()

    #print(q_very)
    if q_very[0] == '1':
        #print('t is 1')
        cnt += 1
    else:
        instruction = q_very.split()
        # 反転していない
        if cnt % 2 == 0:
            if instruction[1] == '1':
                s = instruction[2] + s
            else:
                s = s + instruction[2]
        else:
            if instruction[1] == '1':
                s = s + instruction[2]
            else:
                s = instruction[2] + s

if cnt % 2 != 0:
    s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())

cnt = 0
left = ''
right = ''
for i in range(q):
    q_very = input()

    #print(q_very)
    if q_very[0] == '1':
        #print('t is 1')
        cnt += 1
    else:
        instruction = q_very.split()
        # 反転していない
        if cnt % 2 == 0:
            if instruction[1] == '1':
                left = instruction[2] + left
            else:
                right = right + instruction[2]
        else: # 反転している
            if instruction[1] == '1':
                right = right + instruction[2]
            else:
                left = instruction[2] + left

s = left + s + right

if cnt % 2 != 0:
    s = s[::-1]
print(s)
### BUGGY CODE ###

def is_anagram(string1, string2):
  for a in string1:
    if a not in string2:
      return False
    string2 = string2.replace(a, "", 1)
  if len(string2) == 0:
    return True
  else:
    return False

N = int(input())
strings = [input() for i in range(N)]
ans = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    if is_anagram(strings[i], strings[j]):
      ans += 1
print(ans) 

### FIXED CODE ###

import math
def is_anagram(string1, string2):
  for a in string1:
    if a not in string2:
      return False
    string2 = string2.replace(a, "", 1)
  if len(string2) == 0:
    return True
  else:
    return False

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
anagrams = {}
for i in range(N):
  string = ''.join(sorted(input()))
  if string in anagrams:
    anagrams[string] += 1
  else:
    anagrams[string] = 0

ans = 0
for anagram_num in anagrams.values():
  if anagram_num> 0:
    ans += int(cmb(anagram_num+1,2)) 
print(ans)
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import numpy as np

dp1 = [[0]*T for _ in range(N+1)]
for i,ab in enumerate(AB,1):
  for t in range(1,T):
    a = ab[0]
    if a>t:
      dp1[i][t]=dp1[i-1][t]
      
    else:
      dp1[i][t] = max(dp1[i-1][t],dp1[i-1][t-a]+ab[1])

rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,ab in enumerate(rev_AB,1):
  for t in range(1,T):
    a = ab[0]
    if a>t:
      dp2[i][t]=dp2[i-1][t]
      
    else:
      dp2[i][t] = max(dp2[i-1][t],dp2[i-1][t-a]+ab[1])
      
lis = [0]*N
for i in range(1,N+1):
  for t in range(T):
    lis[i-1] = max(dp1[i-1][t]+dp2[N-i][T-1-t]+AB[i-1][1],lis[i-1])

    
print(max(lis))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))
### BUGGY CODE ###

n,k=map(int,input().split())
ab=[]
for i in  range(n):
    a,b=map(int,input().split())
    x=[a]*b
    ab.extend(x)
ab.sort()
print(ab[k-1])


### FIXED CODE ###

n,k=map(int,input().split())
ab=[]
for i in  range(n):
    a,b=map(int,input().split())
    ab.append([a,b])
ab.sort()
c=0
for i in range(n):
    c+=ab[i][1]
    if c>=k:
        print(ab[i][0])
        exit()
### BUGGY CODE ###

n = int(input())
a_n = list(map(int, input().split()))
a_n.sort()
a_n.reverse()
def check(idx):
    global a_n
    base = a_n[idx]
    count = 0
    dif = 0
    now = a_n[idx]
    while dif <= 2:
        idx += 1
        count += 1
        if(idx == len(a_n)):
            return count
        dif = base - a_n[idx]
        
    return count

ans = -1
for i in  range(n):
    if(ans < check(i)):
        ans = check(i)
print(ans)


### FIXED CODE ###

n = int(input())
a_n = list(map(int, input().split()))
a_n.sort()
a_n.reverse()
def check(idx):
    global a_n
    base = a_n[idx]
    count = 0
    dif = 0
    while dif <= 2:
        idx += 1
        count += 1
        if(idx == n):
            return count
        dif = base - a_n[idx]
    return count

ans = 1
i = 0
c = check(i)
tmp = a_n[0]
while(i != n):
    if(tmp != a_n[i]):
        tmp = a_n[i]
        c = check(i)
    if(ans < c):
        ans = c
    i += 1
print(ans)
### BUGGY CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * k
        k *= 10
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
P = [list(map(int,input().split())) for i in range(Q)]

A = np.array(A)

for item in P:
  np.place(A, A == item[0], item[1])
  print(np.sum(A))


### FIXED CODE ###

import numpy as np
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
P = [list(map(int,input().split())) for i in range(Q)]
A = np.array(A)

sum_A = np.sum(A)
c = collections.Counter(A)
  
for item in P:
  if item[0] in c.keys():
    sum_A += ((item[1] - item[0]) * c[item[0]])
    if item[1] in c.keys():
      c[item[1]] += c[item[0]]
    else:
      c[item[1]] = c[item[0]]
    c.pop(item[0])
  print(sum_A)
### BUGGY CODE ###

h, w = map(int, input().split())

m = []
for i in range(h):
    row = [0 if a == "#" else 1 for a in list(input())]
    m.append(row)

res = 0
for i in range(h):
    for j in range(w):
        a = m[i][j]
        if a == 0:
            continue
        cnt = 1

        k = i -1
        while k >= 0:
            if m[k][j] == 0:
                break
            k -= 1
            cnt += 1

        k = i + 1
        while k < h:
            if m[k][j] == 0:
                break
            k += 1
            cnt += 1

        l = j - 1
        while l >= 0:
            if m[i][l] == 0:
                break
            l -= 1
            cnt += 1

        l = j + 1
        while l < w:
            if m[i][l] == 0:
                break
            l += 1
            cnt += 1

        res = max(res, cnt)

print(res)

### FIXED CODE ###

h, w = map(int, input().split())

m = []
for i in range(h):
    row = list(input())
    m.append(row)

res = 0

mem = [[] for i in range(h)]
dummy = (-1, -1)

for i in range(h):
    _mem = mem[i]
    for j in range(w):
        a = m[i][j]

        if a == "#":
            _mem.append(dummy)
            continue

        c_cnt = 0
        r_cnt = 0

        above = mem[i - 1][j] if i > 0 else dummy
        if above == dummy:
            for ii in range(i + 1, h):
                if m[ii][j] == "#":
                    break
                c_cnt += 1
        else:
            c_cnt = above[0]

        left = mem[i][j - 1] if j > 0 else dummy
        if left == dummy:
            for jj in range(j + 1, w):
                if m[i][jj] == "#":
                    break
                r_cnt += 1
        else:
            r_cnt = left[1]

        res = max(res, c_cnt + r_cnt + 1)
        _mem.append((c_cnt, r_cnt))

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

import numpy as np
N = int(input())
A = tuple(map(int,input().split()))
L = np.array([[int(A[i]^A[i+j] == A[i]+A[i+j]) for i in range(N-j)] + [0]*(j) for j in range(N)])
L[0,:]=1 

R = 0
for i in range(N):
    for j in range(1,N):
        try:
            L[j][i] = L[j][i] and L[j-1][i+1]
            if not L[j][i]:
                L[j:N,i] = 0
                break
        except IndexError:
            break

for i in L:
    a = sum(i)
    if a == 0:
        break
    R += a

print(R)

### FIXED CODE ###

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

result = 0
Right = 0
tmp = 0
for left in range(N):
    for right in range(Right,N):
        if not (tmp & A[right]):
            tmp += A[right]
            Right = right + 1
        else:
            break
    tmp -= A[left]
    result += Right - left
print(result)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

N, As = int(input()), list(map(int, input().split()))
As = [As[i] - i - 1 for i in range(N)]
ans = sys.maxsize
for b in range(min(As), max(As) + 1):
    ans = min(ans, sum(map(lambda A: abs(A - b), As)))
print(ans)

### FIXED CODE ###

N, As = int(input()), map(int, input().split())
As = sorted([A - i - 1 for i, A in enumerate(As)])
b = As[N // 2]
print(sum(map(lambda A: abs(A - b), As)))
### BUGGY CODE ###

N,K=map(int,input().split())
D=[0]*(K+1)
for i in range(1,K+1):
  a=K//i
  D[i]=a**N
ans=0
for i in range(K,0,-1):
  a=K//i
  for j in range(1,a+1):
    if j!=1:
      D[i]-=D[i*j]
  ans+=i*D[i]
  ans%=10**9+7
print(ans%(10**9+7))  


### FIXED CODE ###

N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)
### BUGGY CODE ###

import collections

def comb2(n):
    return int(n * (n - 1) / 2)

def dictcomb(dic, dp):
    ans = 0
    for key in dic:
        ans += dp[dic[key]]
    return ans

def solve(a, dic, dp):
    for i in a:
        dic[i] -= 1
        print(dictcomb(dic, dp))
        dic[i] += 1

def main():
    dp = [comb2(n) for n in range(2 * (10 ** 5) + 1)]
    n = int(input())
    a = list(map(int,input().split()))
    d = collections.Counter(a)
    solve(a, d, dp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def comb2(n):
    return int(n * (n - 1) / 2)

def combdict(dic, dp):
    ans = 0
    for v in dic.values():
        ans += dp[v]
    return ans

def solve(a, dic, dp):
    allsum = combdict(dic,dp)
    for i in a:
        print(allsum - dp[dic[i]] + dp[dic[i]-1])

def main():
    dp = [comb2(i) for i in range(2 * ( 10 ** 5) + 1)]
    n = int(input())
    a = list(map(int,input().split()))
    d = collections.Counter(a)
    solve(a, d, dp)

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

n = int(input())
a = list(map(int,input().split()))
cnt = 1
for i in range(n):
    cnt *= a[i]

if cnt > 10**18:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
cnt = 1
for i in a:
    cnt *= i
    if cnt > 10**18:
        print(-1)
        exit()
print(cnt)
### BUGGY CODE ###

import numpy as np


def main():
    N = int(input())
    A = np.array([])
    B = np.array([])
    for i in range(0, N):
        a, b = map(int, input().split())
        A = np.append(A, [a])
        B = np.append(B, [b])
    
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    sum_AB = A + B
    l = sum_AB.argsort()[::-1]
    for idx, i in enumerate(l):
        if idx % 2 == 0:
            takahashi += A[i]
        else:
            aoki += B[i]

    print(int(takahashi - aoki))


main()


### FIXED CODE ###

import numpy as np


def main():
    N = int(input())
    A = []
    B = []
    for i in range(0, N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    A = np.array(A)
    B = np.array(B)
    sum_AB = A + B
    l = sum_AB.argsort()[::-1]
    takahashi = sum([A[i] for i in [j for idx, j in enumerate(l) if idx % 2 == 0]])
    aoki = sum([B[i] for i in [j for idx, j in enumerate(l) if idx % 2 != 0]])

    print(int(takahashi - aoki))


main()
### BUGGY CODE ###

n = int(input())
a = list(input())
x = [print(a.count(str(i+1))) for i in range(n)]

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0] * n
for i in range(len(a)):
    ans[a[i]-1] += 1
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)
### BUGGY CODE ###

#B問題
N,K = map(int,input().split())
A = list(map(int,input().split()))
rui = [0]

for i in range(N):
    if i == 0:
        rui.append(A[0])
    else:
        rui.append(rui[-1]+A[i])
    
bubun = []
for i in range(N):
    I = i
    for j in range(N-i):
        J = i+j+1
        bubun.append(rui[J]-rui[I])
    
bubun.sort(reverse=True)
m = 40
MAX = 0
kari = 0
while m > 0:
    kari = 2**(m-1)
    count = 0
    for b in bubun:
        if (MAX+kari)&b == MAX+kari:
            count+=1
            
    if count >= K:
        MAX+=kari
    m-=1
    
print(MAX)

### FIXED CODE ###

#B問題
N,K = map(int,input().split())
A = list(map(int,input().split()))
rui = [0]

for i in range(N):
    if i == 0:
        rui.append(A[0])
    else:
        rui.append(rui[-1]+A[i])
    
bubun = []
for i in range(N):
    I = i
    for j in range(N-i):
        J = i+j+1
        bubun.append(rui[J]-rui[I])
    
bubun.sort(reverse=True)
m = 40
MAX = 0
kari = 0
while m > 0:
    kari = 2**(m-1)
    count = 0
    for b in bubun:
        if (MAX+kari)&b == MAX+kari:
            count+=1
            
    if count >= K:
        MAX+=kari
    m-=1
    
print(MAX)
### BUGGY CODE ###

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

for i in range(N):
  target = A[0:i] + A[i+1:N]
  print(max(target))

### FIXED CODE ###

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

max_num = max(A)
max_ind = A.index(max(A))
for i in range(N):
  if max_ind == i:
    print(max(A[0:i]+A[i+1:N]))
  else:
    print(max_num)
### BUGGY CODE ###

from bisect import bisect,bisect_left
import numpy as np
N = int(input())
A = np.int32(input().split())
B = np.int32(input().split())

ans = [0]*29

for k in range(29):
    a = np.sort(np.hstack((A%(2**(k+1)),A%(2**(k+1))-2**(k+1))))
    for b in B:
        b_k = b%(2**(k+1))
        ans[k] += bisect(a,2**(k+1)-1-b_k)-bisect_left(a,2**k-b_k)
        ans[k] %= 2

print(sum([ans[k]*2**k for k in range(29)]))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.int32(input().split())
B = np.int32(input().split())

ans_arr = np.zeros(29,int)
for k in range(29):
    a = np.sort(A%(2**(k+1)))
    b = B%(2**(k+1))
    ans_arr[k] += np.sum(np.searchsorted(a,2**(k+1)-1-b,side='right')-np.searchsorted(a,2**k-b))
    ans_arr[k] += np.sum(N-np.searchsorted(a,3*2**k-b))
    ans_arr[k] %= 2

ans = 0
for k in range(29):
    ans += ans_arr[k]*2**k

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

N = int(input())
count = 0
P = list(map(int,input().split()))
list = [True]*N
for i in range(N):
    for j in range(i):
        if P[i] <= P[j]:
            None
        else:
            list[i] = False
            break
print(list.count(True))

### FIXED CODE ###

N = int(input())
count = 1
P = list(map(int,input().split()))
last_min = P[0]
for n in range(1,N):
    if last_min >= P[n]:
        count += 1
    last_min = min(last_min,P[n])
print(count)