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

h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())


ans_w = [[0] * w for i in range(h)]
ans_h = [[0] * w for i in range(h)]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == '#': continue
        if ans_w[i][j] != 0: continue

        while j + cnt < w:
            if s[i][j + cnt] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_w[i][j + k] = cnt
# print(ans_w)

for i in range(w):
    for j in range(h):
        cnt = 0
        if s[j][i] == '#': continue
        if ans_h[j][i] != 0: continue

        while j + cnt < h:
            if s[j + cnt][i] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_h[j + k][i] = cnt
# print(ans_h)

out = 0
for i in range(h):
    for j in range(w):
        out = max(out, ans_h[i][j] + ans_w[i][j])

print(out - 1)


### FIXED CODE ###

h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(input())


ans_w = [[0] * w for i in range(h)]
ans_h = [[0] * w for i in range(h)]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == '#': continue
        if ans_w[i][j] != 0: continue

        while j + cnt < w:
            if s[i][j + cnt] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_w[i][j + k] = cnt
# print(ans_w)

for i in range(w):
    for j in range(h):
        cnt = 0
        if s[j][i] == '#': continue
        if ans_h[j][i] != 0: continue

        while j + cnt < h:
            if s[j + cnt][i] == '#': break
            cnt += 1

        for k in range(cnt):
            ans_h[j + k][i] = cnt
# print(ans_h)

out = 0
for i in range(h):
    for j in range(w):
        out = max(out, ans_h[i][j] + ans_w[i][j])

print(out - 1)
### BUGGY CODE ###

S = input()

mod = 10**9+7
N = len(S)

s = S[-1]
dp = [0]*13
if s=="?":
    dp[:10] = [1]*10
else:
    dp[int(s)] = 1

for c,s in enumerate(S[:-1][::-1],1):
    dp2 = [0]*13
    if s=="?":
        for i in range(10):
            for j,n in enumerate(dp):
                dp2[(i*(10**c)+j)%13] += n
    else:
        i = int(s)
        for j,n in enumerate(dp):
            dp2[(i*(10**c)+j)%13] += n
    dp = [n%mod for n in dp2]
print(dp[5])

### FIXED CODE ###

S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])
### BUGGY CODE ###

N, K = map(int, input().split())
ans = 0
for i in range(N):
    tmp = i
    memo = 0
    while tmp < K:
        memo += 1
        tmp *= 2
    ans += 0.5 ** memo
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
ans = 0
for i in range(1,N+1):
    tmp = i
    memo = 0
    while tmp < K:
        memo += 1
        tmp *= 2
    ans += 0.5 ** memo
print(ans/N)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]
memo = {}


def dfs(m):
    if m in memo:
        return memo[m]
    for i in range(q):
        if word[m] == li[i][0]:
            if li[i][1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            memo[m] = 'Left'
            return 'Left'
        elif m > n-1:
            memo[m] = 'Right'
            return  'Right'
    memo[m] = True
    return True

def left(a,b):
    m = int((a+b)/2)
    if a == m:
        return b
    if dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    m = int((a+b)/2)
    if a == m:
        return a
    if dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

if dfs(0) == 'Right':
    print(0)
elif dfs(0) == 'Left':
    if dfs(n-1) == 'Right':
        print(right(0,n-1) - left(0,n-1) + 1)
    elif dfs(n-1) == 'Left':
        print(0)
    else:
        print(n - left(0,n-1))
else:
    if dfs(n-1) == 'Right':
        print(right(0,n-1) + 1)
    elif dfs(n-1) == 'Left':
        print(0)
    else:
        print(n)


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
word = list(s)
li = [list(input().split()) for _ in range(q)]
memo = {}

def dfs(m):
    k = m
    if m in memo:
        return memo[m]
    for x in li:
        if word[m] == x[0]:
            if x[1] == 'R':
                m += 1
            else:
                m -= 1
        if m < 0:
            memo[k] = 'Left'
            return 'Left'
        elif m > n-1:
            memo[k] = 'Right'
            return  'Right'
    memo[k] = True
    return True

def left(a,b):
    m = int((a+b)/2)
    if a == m:
        return b
    elif dfs(m) == 'Left':
        return left(m,b)
    else:
        return left(a,m)

def right(a,b):
    m = int((a+b)/2)
    if a == m:
        return a
    elif dfs(m) == 'Right':
        return right(a,m)
    else:
        return right(m,b)

if dfs(0) == 'Right':
    print(0)
elif dfs(0) == 'Left':
    if dfs(n-1) == 'Right':
        print(right(0,n-1) - left(0,n-1) + 1)
    elif dfs(n-1) == 'Left':
        print(0)
    else:
        print(n - left(0,n-1))
else:
    if dfs(b) == 'Right':
        print(right(0,n-1) + 1)
    elif dfs(b) == 'Left':
        print(0)
    else:
        print(n)
### BUGGY CODE ###

n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
mark=[0]*(n-k+1)
m=[1]*(k+1)
for i in range(k):
  m[i+1]=a[i]*m[i]
mark[0]=m[k]
for j in range(1,n-k+1):
  mark[j]=(mark[j-1]/a[j-1])*a[j+k-1]
  if mark[j-1]<mark[j]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
for i in range(n-k):
  if a[i]<a[i+k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

def prime_factorize(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

primes = defaultdict(int)
for a in A:
    for x, p in prime_factorize(a):
        primes[x] = max(primes[x], p)
lcm = 1
for prime, ind in primes.items():
    lcm *= prime ** ind
ans = 0
for i in range(N):
    ans += lcm // A[i]
    ans %= mod
print(ans)


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

def prime_factorize(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

primes = defaultdict(int)
for a in A:
    for x, p in prime_factorize(a):
        primes[x] = max(primes[x], p)
lcm = 1
for prime, ind in primes.items():
    lcm *= prime ** ind
ans = 0
for i in range(N):
    ans += lcm // A[i]
    if i == N // 2:
        ans %= mod
print(ans % mod)
### BUGGY CODE ###

N = int(input())
for i in range(1, pow(10, 9)):
	if i % 2 == 0 and i % N == 0:
		print(i)
		break

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
	print(N)
else:
	print(2 * N)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from fractions import Fraction
def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N)]
    MOD = 10**9+7

    from collections import Counter
    ctr = Counter()
    az = bz = zz = 0
    for a,b in AB:
        if a==b==0:
            zz += 1
        elif a==0:
            az += 1
        elif b==0:
            bz += 1
        else:
            f = Fraction(a,b)
            ctr[f] += 1
    ans = pow(2,az,MOD) + pow(2,bz,MOD) - 1

    used = set()
    for f1,v in ctr.items():
        if f1 in used: continue
        f2 = -1/f1
        if f2 in ctr:
            used.add(f2)
        r = pow(2,v,MOD) + pow(2,ctr[f2],MOD) - 1
        ans *= r
        ans %= MOD
    ans += zz - 1
    ans %= MOD
    print(ans)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import gcd
def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N)]
    MOD = 10**9+7

    from collections import Counter
    ctr = Counter()
    az = bz = zz = 0
    for a,b in AB:
        if a==b==0:
            zz += 1
        elif a==0:
            az += 1
        elif b==0:
            bz += 1
        else:
            g = gcd(a,b)
            a,b = a//g, b//g
            if b < 0:
                b *= -1
                a *= -1
            ctr[(a,b)] += 1
    ans = pow(2,az,MOD) + pow(2,bz,MOD) - 1

    used = set()
    for (a1,b1),v in ctr.items():
        if (a1,b1) in used: continue
        a2,b2 = -b1,a1
        if b2 < 0:
            b2 *= -1
            a2 *= -1
        if (a2,b2) in ctr:
            used.add((a2,b2))
        r = pow(2,v,MOD) + pow(2,ctr[(a2,b2)],MOD) - 1
        ans *= r
        ans %= MOD
    ans += zz - 1
    ans %= MOD
    print(ans)
solve()
### BUGGY CODE ###

def func(x):
    return int(x)-1
N, K = list(map(int, input().split()))
A = list(map(func, input().split()))


now = 0
past = []

for i in range(N):
    if now in past:
        break
    past.append(now)
    now = A[now]



i_loop = past.index(now)
loop = past[i_loop:]
if K >= i_loop:
    print(loop[(K-i_loop) % len(loop)] +1)
else:
    print(past[K] +1)



### FIXED CODE ###

def func(x):
    return int(x)-1
N, K = list(map(int, input().split()))
A = list(map(func, input().split()))



now = 0
past = []
past_set = set()

for i in range(N):
    if now in past_set:
        break
    past.append(now)
    past_set.add(now)
    now = A[now]


i_loop = past.index(now)
loop = past[i_loop:]
if K >= i_loop:
    print(loop[(K-i_loop) % len(loop)] +1)
else:
    print(past[K] +1)
### BUGGY CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    intersects = set()
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            intersects = set(range(o[0], o[1]+1))
        else:
            intersects = intersects & set(range(o[0], o[1]+1))

    print(len(intersects))


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            lmax = o[0]
            rmin = o[1]
        else:
            lmax = max(lmax, o[0])
            rmin = min(rmin, o[1])

    print(rmin-lmax+1 if lmax <= rmin else 0)


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

N = int(input())
P = list(map(int,input().split()))
count = 1

for i in range(1, N):
  isbreak = False
  for j in range(0,i):
    if (P[i] > P[j]):
      isbreak = True
      break
  if isbreak == False:
    count += 1
    
print(count)
  

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
count = 1
 
if N > 0:
  min = P[0]
  
for i in range(1, N):
  isbreak = False
  
  if min < P[i]:
    continue
  elif min >= P[i]:
    min = P[i]
    count += 1
    continue  
  for j in range(0,i):
    if (P[i] > P[j]):
      isbreak = True
      break
  if isbreak == False:
    count += 1
    
print(count)
### BUGGY CODE ###

import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)

### FIXED CODE ###

import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())

s = input()

for _ in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())

s = input()

count = [0] * n

for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        count[i] += 1

from itertools import accumulate

accum = list(accumulate(count))

for _ in range(q):
    l, r = map(int, input().split())
    print(accum[r-1] - accum[l-1])
### BUGGY CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  print(dp[n-1])
main()


### FIXED CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())
### BUGGY CODE ###

n = int(input())
x = int(input(), 2)

def solve(a, pc):
    if pc == 0:
        return 0
    elif pc == 1:
        return 1
    return solve(a % pc, bin(a % pc).count('1')) + 1
        
pc = bin(x).count('1')
pc_p = pc + 1
pc_m = pc - 1
for i in reversed(range(n)):
    if x >> i & 1 == 1:
        a = x - pow(2, i)
        print(solve(a, pc_m))
    else:
        a = x + pow(2, i)
        print(solve(a, pc_p))


### FIXED CODE ###

n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)
### BUGGY CODE ###

n = int(input())
S = input()
dp = [[0]*n for _ in range(n)]
for i in range(n-1, -1, -1):
  for j in range(n-1, -1, -1):
    if i == n-1:
      dp[i][j] = int(S[i] == S[j])
    elif j == n-1:
      dp[i][j] = dp[j][i]
    else:
      if S[i] == S[j]:
        dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
  for j in range(n):
    ans = max(ans, min(dp[i][j], j-i))
print(ans)

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

n = int(input())
s = input()
ans = 0
for i in range(n):
  A = z_algo(s[i:])
  for j in range(1, n-i):
    m = min(j, A[j])
    ans = max(m, ans)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
n_count = []
for a in set(A):
    n_count.append(A.count(a))
print(sum(sorted(n_count)[:len(set(A)) - K]))


### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
A = list(map(int, input().split()))
a = Counter(A)
a = sorted(a.values())
print(sum(a[:len(a) - k]))
### BUGGY CODE ###

N,A,B=map(int,input().split())
count=0
while N>0:
  for i in range(A):
    if N>0:
      count+=1
      N-=1
    else:
      break
  for i in range(B):
    if N>0:
      N-=1
    else:
      break
print(count)

### FIXED CODE ###

N,A,B=map(int,input().split())
a=int(N//(A+B))
b=N%(A+B)
if b>A:
  b=A
print(A*a+b)
### BUGGY CODE ###

from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = C
        dp[B][A] = C

    for i in range(N):
        dp[i][i] = 0

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                if dp[s][m] != INF and dp[m][e] != INF:
                    dist = dp[s][m] + dp[m][e]
                    if dist < dp[s][e]:
                        dp[s][e] = dist

    ans = INF
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
            if total >= ans:
                break
        else:
            if total < ans:
                ans = total
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
from itertools import product, groupby, permutations
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    N, M, R = map(int, input().split())
    r_list = list(map(int, input().split()))
    dp = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        dp[A][B] = dp[B][A] = C

    for i in range(N):
        dp[i][i] = 0

    for m in range(N + 1):
        for s in range(N + 1):
            for e in range(N + 1):
                dist = dp[s][m] + dp[m][e]
                if dist < dp[s][e]:
                    dp[s][e] = dist

    ans = float("inf")
    for p in permutations(r_list, len(r_list)):
        total = 0
        for i in range(len(p) - 1):
            total += dp[p[i]][p[i + 1]]
            if total >= ans:
                break
        else:
            if total < ans:
                ans = total
    print(ans)

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

from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def BFS():
  node_sequences = [[] for _ in range(n)]
  visited = [False]*n
  queue_nodes = deque()
  queue_nodes.append((0, []))
  while queue_nodes:
    (vertex, sequence) = queue_nodes.popleft()
    visited[vertex] = True
    node_sequences[vertex] = sequence + [a[vertex]]
    for node in adjacent[vertex]:
      if not visited[node]:
        queue_nodes.append((node, node_sequences[vertex]))
  return node_sequences
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
long_sequences = BFS()
[print(longest_subsequence(sequence)) for sequence in long_sequences]

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# sys.exit()
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()
    #N = 2000
    #S = "a"*N
    import time
    star = time.time()
    
    from collections import defaultdict
    D = {}
     
    for i in range(N):
        s = S[i]
        if not s in D:
            D[s] = [1, i, i]
        else:
            D[s][-1] = i
        for j in range(i+1,min(i+2+N//2, N, max(2*i+2,(N+i)//2+2))):
            s = "".join([s,S[j]])
            if not s in D:
                D[s] = [j-i+1, i, i]
            else:
                D[s][-1] = i
    totyuu = time.time()
    #print(totyuu-star)
        
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if len(D[i]) >= 3:
            if D[i][1] + L <= D[i][-1]:
                tmp = L
        if ans < tmp:
            ans = tmp
    g = time.time()
    #print(g-star)
    print(ans)
    
main()



### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    A = [[] for i in range(N)]
    for i in range(N):
        A[i] = [0]*i + z_algo(S[i:])
    ans = 0
    for i in range(N):
        for j in range(N):
            if i + A[i][j] <= j and ans < A[i][j]:
                ans = A[i][j]
    
    g = time.time()
    #print(g-star)
    print(ans)
    
main()