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

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    while num%2==0:
        d.add(2)
        num //= 2
    for i in range(3,int(sqrt(num))+1,2):
        while num%i==0:
            d.add(i)
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {}
    for i in x:
        for j in pfact(i):
            if dt.get(j,1):
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)
### BUGGY CODE ###

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
A,B,C,K = LI()
ans = 0
for _ in range(K):
    if A!=0:
        ans +=1
        A -= 1
    elif B!=0:
        B -= 1
    else:
        ans -= 1
print(ans)


### FIXED CODE ###

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
A,B,C,K = LI()
ans = min(A,K)
if A+B<K:
    ans -= K-(A+B)
print(ans)
### BUGGY CODE ###

N=int(input())
sisterN=[]
SISTERn=[]
SISterN=[]
for n in range(N):
    _=int(input())
    if _<40000:
        _s= _
        if sisterN.count(_s)==1:
            sisterN.remove(_s)
        else:
            sisterN.append(_s)
    elif 40001<_<99000:
        _m= _
        if SISterN.count(_m)==1:
            SISterN.remove(_m)
        else:
            SISterN.append(_m)
    elif 99001<_:
        _b= _
        if SISTERn.count(_b)==1:
            SISTERn.remove(_b)
        else:
            SISTERn.append(_b)

print(len(sisterN)+len(SISTERn)+len(SISterN))



### FIXED CODE ###

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

for n in range(N):
    _=int(input())
    if _ in S:
        S.remove(_)
    else:
        S.add(_)

print(len(S))
### BUGGY CODE ###

from functools import reduce
N = int(input())
A = map(int, input().split())
B = reduce((lambda x, y : x*y), A)
if B > 10**18:
  print(-1)
else:
  print(B)


### FIXED CODE ###

from functools import reduce
N = int(input())
A = list(map(int, input().split()))
A.sort()
if A[0] == 0:
    print(0)
else:
    p = 1;
    for i in range(N):
        p *= A[i];
        if p > 10**18:
            p = -1;
            break;
    print(p)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

x = input()

for i in range(0, int(len(x)/2)):
    x = x.replace("ST", "")

print(len(x))


### FIXED CODE ###

# -*- coding: utf-8 -*-

x = input()

# ペアになっていないSの数（ペアができたら-1）
sc = 0
# ペアにならなかったTの数
tc = 0

for c in x:
    if c == 'S':
        sc += 1
    elif sc >= 1:
        sc -= 1
    else:
        tc += 1

print(sc + tc)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
result = 0
for i in range(N-K+1):
    if result <= sum(p[i:i+K]):
        result = sum(p[i:i+K])
    else:
        None
print((result+K)/2)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
result = 0
p_t = [0]
for i in range(N):
    p_t.append(p[i]+p_t[i])
ans = p_t[K] - p_t[0]

for i in range(N-K):
    tmp = p_t[i+1+K] - p_t[i+1]
    if ans < tmp:
        ans = tmp
print((ans+K)/2)
### BUGGY CODE ###

H,W=map(int,input().split())
c=[input() for i in range(H)]
dp=[[[0 for i in range(H+1)] for j in range(H+1)] for k in range(W-1)]

for i in range(W-1):
    for j in range(1,H+1):
        for k in range(1,H+1):
            cost=sum(c[j-l-1][i]==c[k-l-1][i+1] for l in range(0,min(j,k)))
            dp[i][j][k]=cost+min(dp[i][j-1][k],dp[i][j][k-1])

res=sum(dp[i][H][H] for i in range(W-1))

print(res)


### FIXED CODE ###

H,W=map(int,input().split())
c=[input() for i in range(H)]
res=0
for i in range(W-1):
    dp=[[0 for j in range(H+1)] for k in range(H+1)]
    table=[[0 for j in range(H+1)] for k in range(H+1)]
    for j in range(1,H+1):
        for k in range(1,H+1):
            table[j][k]=table[j-1][k-1]+(c[j-1][i]==c[k-1][i+1])

    for j in range(1,H+1):
        for k in range(1,H+1):
            cost=table[j][k]
            dp[j][k]=cost+min(dp[j-1][k],dp[j][k-1])
    res+=dp[H][H]

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

def main():
    S = [input()]
    Q = int(input())
    is_turned = False

    for _ in range(Q):
        query = input()
        if query == "1":
            is_turned = not is_turned
        else:
            T, F, C = query.split()
            if is_turned ^ (F == "1"):
                S = [C] + S
            else:
                S = S + [C]

    if (is_turned):
        print("".join(S)[::-1])
    else:
        print("".join(S))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    L = ""
    R = ""
    is_turned = False

    for _ in range(Q):
        Query = input().split()
        if Query[0] == "1":
            is_turned = not is_turned
        else:
            if is_turned ^ (Query[1] == "1"):
                # L.insert(0, Query[2])
                L = Query[2] + L
            else:
                # R.append(Query[2])
                R = R + Query[2]

    if (is_turned):
        print("".join(L + S + R)[::-1])
    else:
        print("".join(L + S + R))


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

n = int(input())
l = list(map(int,input().split()))
count = 0
l.sort(reverse=True)
for i in range(n-2):
  for j in range(i+1,n-1):
    tmp = [k for k, x in enumerate(l[(j+1):]) if x > l[i]-l[j]]
    if len(tmp) != 0:
      count += tmp[-1]+1
print(count)

### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    count+=bisect_left(l,l[j]+l[i])-j-1
print(count)
### BUGGY CODE ###

s = input()

s = s[::-1]

dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]


if s[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1,len(s)):
    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                dp[i][(j*(10**i)+k)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i][(int(s[i])*(10**i) + k) %13] += dp[i-1][k]
    for k in range(13):
        dp[i][k] = dp[i][k] % (10**9 +7)

print(dp[len(s)-1][5] % (10**9 + 7) )

### FIXED CODE ###

s = input()
 
s = s[::-1]
 
dp = [[0 for _ in range(13)] for __ in range(len(s)+1)]
 
l = len(s)
 
 
if s[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1
 
m = 1
MOD = 10**9 +7
 
for i in range(1,len(s)):
    m = m*10 % 13
 
    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
                dp[i][k] %= MOD
    else:
        for k in range(13):
            dp[i][(int(s[i])*m + k) %13] += dp[i-1][k]
            dp[i][k] %= MOD
 
print(dp[len(s)-1][5] % MOD )
### BUGGY CODE ###

n = int(input())
ll = list(map(int,input().split()))
mm = []
pp = n
i = 0
while pp > 0:
    mm.append(ll[-1-i])
    ll[-1-i] = -1
    i = i + 2
    pp = pp -2
    
for i in range(len(ll)):
    if ll[i] > -1:
        mm.append(ll[i])
    else:
        None
        
sss = ''
for i in range(len(mm)):
    if i != 0:
        sss = sss + ' ' + str(mm[i])
    else:
        sss = sss + str(mm[i])
        
print(sss)

### FIXED CODE ###

n = int(input())
ll = list(map(int,input().split()))
mm = []
pp = n
i = 0
for i in range(n):
    try:
        mm.append(str(ll[-1-2*i]))
        ll[-1-2*i] = '-1'
    except:
        pass

    
for i in range(len(ll)):
    if ll[i] != '-1':
        mm.append(str(ll[i]))
    else:
        None
        
sss = ''
for i in mm:
    print(i, end= ' ')
### BUGGY CODE ###

def takein(p):
    s = 0
    track = 1
    for i in range(n):
        if s + w[i] <= p:
            s += w[i]
        else:
            track += 1
            if track > k: return False
            s = w[i]
    return True

n, k = map(int, input().strip().split())
w = []
for i in range(n):
    w.append(int(input()))

p = max(max(w), sum(w) // k)
while not takein(p):
    p += 1

print(p)

### FIXED CODE ###

def check(p):
    s = w[0]
    track = 1
    for i in range(1, n):
        if s + w[i] <= p:
            s += w[i]
        else:
            track += 1
            if track > k: return False
            s = w[i]
    return True

n, k = map(int, input().strip().split())
w = []
for i in range(n):
    w.append(int(input()))

L = max(w)
if check(L):
    print(L)
else:
    R = sum(w)
    assert check(R)

    while L + 1 < R:
        M = (L + R) // 2
        if check(M):
            R = M
        else:
            L = M

    print(R)
### BUGGY CODE ###

def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        if now not in history:
            history.append(now)
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            # 末尾未満
            skip = len(history)-history.index(now)-1
            now = history[history.index(now)+skip]
            i += skip

    print(now+1)

main()


### FIXED CODE ###

def main():
    # 町の数N, 町iの転送先はindexがAi-1の町
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    # K回移動した時の町番号を出力
    # もし一度出てきた番号が出てきたら記憶している道順リストを使う
    # 最初は道を覚えさせる作業が必要
    now = 0
    history = [0]
    isVisited = [False for i in range(N)]
    i = 0
    while i<K:
        # まず進む
        now = A[now]-1
        # 道順登録
        #if now not in history:
        if isVisited[now] == False:
            history.append(now)
            isVisited[now] = True
            i+=1
        # 以前出てきてる町ならそこから末尾までを自動で進めてiのカウントも進める
        else:
            start = history.index(now)
            r = start + (K-1-i)%(len(history)-start)
            now = history[r]
            break

    print(now+1)

main()
### BUGGY CODE ###

import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, M = tuple(li())
A = list(li())
heapq.heapify(A)
def update(pq, k, val):
    # update pq in place
    for _ in range(k):
        cur = heapq.heappop(pq)
        if cur < val:
            heapq.heappush(pq, val)
        else:
            heapq.heappush(pq, cur)
            break
for i in range(M):
    k, val = tuple(li())
    update(A, k, val)

print(sum(A))


### FIXED CODE ###

import heapq
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def ii(): return int(stdin.readline())
def li(): return map(int, stdin.readline().split())
N, M = tuple(li())
A = list(li())
heapq.heapify(A)
def update(pq, k, val):
    # update pq in place
    for _ in range(k):
        cur = heapq.heappop(pq)
        if cur < val:
            heapq.heappush(pq, val)
        else:
            heapq.heappush(pq, cur)
            break

ops = []
# val, k_sum
keep = dict()
for i in range(M):
    k, val = tuple(li())
    k_sum = keep.get(val, 0)
    keep[val] = k_sum + k

for val, k in keep.items():
    update(A, k, val)

print(sum(A))
### BUGGY CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える

N,Q = map(int,input().split())
s = str(input())
T = []
D = []
for i in range(Q):
    t,d = map(str,input().split())
    T.append(t)
    D.append(d)

golem = [1 for i in range(N)]

positions = {}
for i in range(len(s)):
    if s[i] in positions.keys():
        tmp =  positions[s[i]]
        tmp.append(i)
        positions[s[i]] = tmp
    else:
        positions[s[i]] = [i]
# print(positions)
ans = N

for i in range(Q):
    if T[i] in positions.keys():
        move_poss = positions[T[i]]
        # print(golem)
        if D[i] == "R":
            move_poss.reverse()
            for move in move_poss:
                if move == N-1:
                    ans -= golem[N-1]
                    golem[N-1] = 0
                else:
                    golem[move+1] += golem[move]
                    golem[move] = 0

        else:
            for move in move_poss:
                if move == 0:
                    ans -= golem[0]
                    golem[0] = 0
                else:
                    golem[move-1] += golem[move]
                    golem[move] = 0

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える

N,Q = map(int, input().split())
s = input()
td = [input().split() for i in range(Q)]

td.reverse()

nl = 0
nr = N-1
L = []
R = []
for i in td:#全ての指示
    # print(L,R)
    if i[1]=="L":
        if nl < N:
            if s[nl] == i[0]:
                L.append(i[0])
                nl += 1
            if len(R) != 0:
                if R[-1]==i[0]:
                    R.pop()
                    nr += 1
    else:
        if nr >= 0:
          if s[nr] == i[0]:
            R.append(i[0])
            nr -= 1
        if len(L) != 0:
          if L[-1] == i[0]:
            L.pop()
            nl -= 1

print(N-len(L)-len(R))
### BUGGY CODE ###

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

Z = [0 for _ in range(N)]
Z[0] = N

def momokuroz(s):
  n = len(s)
  z = [0 for _ in range(n)]
  z[0] = n
  i = 1; j = 0
  while i < n: #iは基準の位置。
    while i+j < n and s[i+j] == s[j]:
      j += 1 #何文字一致してるかなー？
    z[i] = min(i,j) #jが一致している文字数。
    if j == 0:
      i += 1
      continue
    
    k = 1 #途中でjを超えていたらその先は別途見る必要がある。
    #kが一致してる文字数ぴったしだとその先は不明。k<j
    #j文字一致しているところを参照したいが飛び出していたらそこは不明。k+Z[k]<j
    while k<j and k+z[k] <j:
      z[i+k] = z[k]
      k += 1
    
    i += k #基準位置を動かす
    j -= k #このjまでは一致しているのは確定なので上のWhileに戻ってチェック。
  #MAX = max(z[1:])
  #print(MAX,s)
  return z

ans = 0    
for i in range(N-1):
  temp = S[i:]
  t = momokuroz(temp)
  #print(t,max(t[1:]))
  ans = max(ans,max(t[1:]))    


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 ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = list(map(int, input().split()))

a_count_list = []

a_dic = {}

for i in range(len(a_list)):
    key = a_list[i]
    if key in a_dic:
        a_dic[key] += 1
    else:
        a_dic[key] = 1

a_solution_dic = {}
a_solution_dic_at_k = {}
for key in a_dic:
    a_solution_dic[key] = int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)


for k, ak in enumerate(a_list):
    sum_select = 0
    sum_select += int((a_dic[ak]-1) * (a_dic[ak]-2) / 2)
    for key in a_solution_dic:
        if key != ak:
            sum_select += a_solution_dic[key]


    print(sum_select)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# input
n = int(input())
a_list = []
a_dic = {}
for ai in input().split():
    int_ai = int(ai)
    a_list.append(int_ai)
    if int_ai in a_dic:
        a_dic[int_ai] += 1
    else:
        a_dic[int_ai] = 1

a_solution_dic = {}
all_sum_select = 0
for key in list(a_dic.keys()):
    all_sum_select += int(a_dic[key] * (a_dic[key]-1) / 2)
    #a_solution_dic_at_k[key] = int((a_dic[key]-1) * (a_dic[key]-2) / 2)

for k, ak in enumerate(a_list):
    sum_select_at_k = all_sum_select + int((a_dic[ak]-1) * (a_dic[ak]-2) / 2) \
                       - int(a_dic[ak] * (a_dic[ak]-1) / 2)


    print(sum_select_at_k)
### BUGGY CODE ###

K,S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count += 1
print(count)

### FIXED CODE ###

K,S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        if 0<=S-x-y<=K:
            count += 1
print(count)
### BUGGY CODE ###

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = [[int(p) for p in i.split()] for i in _input[1:n]]

if not edge:
    print(k)
else:
    import collections

    colored  = {}
    edge_map = collections.defaultdict(list)
    for e in edge:
        edge_map[e[0]].append(e[1])
        edge_map[e[1]].append(e[0])

    root = edge[0][0]
    colored[root] = k
    for i, p in enumerate(edge_map[root]):
        colored[p] = k - (i + 1)

    visit = []
    visit.extend(edge_map[root])
    while len(colored) != n:
        current = visit.pop(0)
        not_colored = [p for p in edge_map[current] if p not in colored and p not in visit]
        visit = not_colored + visit
        for i, p in enumerate(not_colored):
            colored[p] = k - (i + 2)

    total = 1
    for i in colored.values():
        total *= i
        if total > 1000000007:
            total %= 1000000007
    print(total)


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

_input = [i for i in open(0).read().split('\n') if i]
n, k = [int(i) for i in _input[0].split()]
edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])

factorial = [0] * (k + 1)
inverse = [0] * (k + 1)
MOD = 1000000007

# Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
def mod_pow1(n, k, mod):
    a = 1
    while k:
        if (k & 1) == 1:
            a = (a * n) % mod
        n = (n * n) % mod
        k >>= 1
    return a

# Ref: https://www.smartbowwow.com/2018/10/mod1097.html
def mod_pow2(n, k, mod):
    if k == 0:
        return 1
    if k % 2 == 0:
        a = mod_pow2(n, k // 2, mod)
        return (a * a) % mod
    else:
        return (n * mod_pow2(n, k - 1, mod)) % mod

#mod_pow = mod_pow1
# It's better to use built-in function for speed.
mod_pow = pow

def mod_factorial_inverse(k, mod):
    factorial[0] = 1
    inverse[0] = 1

    # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    for i in range(1, k + 1):
        factorial[i] = ((i * factorial[i - 1]) % mod) # factrial[i]
        inverse[i] = mod_pow(factorial[i], mod - 2, mod) # inverse[i]
 
total = 1

if not edge:
    print(k)
else:
    all_edge = tuple([[] for _ in range(n + 1)])
    for e in edge:
        all_edge[e[0]].append(e[1])
        all_edge[e[1]].append(e[0])
    all_edge = [set(v) for v in all_edge]

    if [v for v in all_edge if len(v) >= k]:
        print(0)
    else:
        mod_factorial_inverse(k, MOD)

        root = edge[0]
        total = (factorial[k] * inverse[k - len(all_edge[root[0]]) - 1]) % MOD

        def dfs(current, from_):
            global total
            child = all_edge[current]
            if len(child) - 1 > 0:
                total = (total * factorial[k - 2] * inverse[k - 2 - (len(child) - 1)]) % MOD
            for c in child:
                if c != from_:
                    dfs(c, current)
        for c in all_edge[root[0]]:
            dfs(c, root[0])
        print(total)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    for i in range(1, n):
        for j in reversed(range(i-ans)):
            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
    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()