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

s = input().rstrip()

pp = prev = [0]*len(s)
cur = [1]*len(s)

cnt = 0
while cur!=prev and cur!=pp:
    cnt = not cnt
    tmp = [0]*len(s)
    for i, c in enumerate(s):
        if c == 'R':
            tmp[i+1] += cur[i]
        else:
            tmp[i-1] += cur[i]
    pp,prev,cur = prev,cur,tmp

if cnt:
    print(*prev)
else:
    print(*cur)

### FIXED CODE ###

s = input().rstrip() + 'X'

r_cnt = l_cnt = 0
is_r = True
begin_l = None
ans = [0] * (len(s)-1)
for i in range(len(s)):
    if is_r and s[i] == 'R':
#         print(f'{i}: R')
        r_cnt += 1
    elif not is_r and s[i] == 'L':
#         print(f'{i}: L')
        l_cnt += 1
    elif s[i] == 'L':
#         print(f'{i}: R>L')
        is_r = False
        l_cnt = 1
        begin_l = i
    else:
#         print(f'{i}: L>?')
        is_r = True
#         print(l_cnt, r_cnt)
        tot = l_cnt + r_cnt
        small = tot//2
        large = tot - small
        if r_cnt%2:
            ans[begin_l-1] = large 
            ans[begin_l] = small
        else:
            ans[begin_l-1] = small
            ans[begin_l] = large
        r_cnt = 1
        l_cnt = 0

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

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    print(a.index(i)+1,end=" ")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b={}
cnt=1;
for i in a:
    b[i]=cnt
    cnt+=1
for i in range(1,n+1):
    print(b[i], end=" ")
### BUGGY CODE ###

s = raw_input()

head = []
sub = 0

for i, v in enumerate(s):
    if v == 'S':
        head.append(i)

    if v == 'T' and head:
        head.pop(0)
        sub += 2

print(len(s) - sub)

### FIXED CODE ###

s = input()

now_try = 0
idx = 0
while idx < len(s) - 1:

    if s[idx] == 'T':
        idx += 1
        continue

    if s[idx] == 'S':
        if s[idx + 1] == 'T':
            s = s[:idx] + s[idx + 2:]
            now_try += 1
            idx = idx - 1 if idx - 1 >= 0 else 0
        else:
            idx += 1

print(len(s))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, b + 1):
    if i < a + k or i > b - k:
        print(i)


### FIXED CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(a + k, b + 1)):
    print(i)
for i in range(max(a + k, b - k + 1), b + 1):
    print(i)
### BUGGY CODE ###

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())
  
for i in range(N):
  A_temp = A[i]
  A[i] = 0
  print(max(A))
  A[i] = A_temp

### FIXED CODE ###

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())
  
A_Max = sorted(A)[-1]
A_2nd = sorted(A)[-2]

for i in range(N):
  if A[i] == A_Max:
    print(A_2nd)
  else:
    print(A_Max)
### BUGGY CODE ###

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

from itertools import accumulate
acc = [0]+list(accumulate(As))
dp = [0] * 50
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 最大の桁数
for d in range(50):
    if max(sums) & (1<<d):
        mx = max(mx, d)
        dp[d] += 1
mx = 0
for i in range(50):
    if dp[i] >= k:
        mx = max(mx,i)

ans = 0
now = 0
for d in range(50,-1,-1):
    cnt = 0
    for s in sums:
        if s & (now+(1<<d)) == now+(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now += 1<<d
print(now)

### FIXED CODE ###

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

from itertools import accumulate
acc = [0]+list(accumulate(As))
dp = [0] * 50
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 最大の桁数
for d in range(50):
    if max(sums) & (1<<d):
        mx = max(mx, d)
        dp[d] += 1
mx = 0
for i in range(50):
    if dp[i] >= k:
        mx = max(mx,i)

# 計算
ans = 0
now = 0
for d in range(50,-1,-1):
    cnt = 0
    for s in sums:
        if s & (now+(1<<d)) == now+(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now += 1<<d
print(now)
### BUGGY CODE ###

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N

for i in range(N):
  w, v = map(int, input().split())
  ws[i] = w
  vs[i] = v
V = sum(vs)+1
  

dp = [[float('inf')]*V for _ in range(N+1)]
# dp[i][j]: i個の品物までを見てjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w = ws[i]
  v = vs[i]
  for j in range(i, -1, -1):
    for k in range(V):
      if k-v>=0:
        dp[j+1][k] = min(dp[j][k-v]+w, dp[j+1][k])
      dp[j+1][k] = min(dp[j][k], dp[j+1][k])

for j in range(V-1, -1, -1):
  if dp[N][j] <= W:
    print(j)
    exit()

### FIXED CODE ###

N, W = map(int, input().split())
ws = [0]*N
vs = [0]*N

for i in range(N):
  w, v = map(int, input().split())
  ws[i] = w
  vs[i] = v

V = N*(10**3)+1
dp = [[float('inf')]*V for _ in range(N+1)]
# dp[i][j]: i個の品物までを見てjの価値を実現する最小のw
dp[0][0] = 0
temp = 0

for i in range(N):
  w = ws[i]
  v = vs[i]
  for k in range(V):
    if k-v>=0:
      dp[i+1][k] = min(dp[i][k-v]+w, dp[i+1][k])
    dp[i+1][k] = min(dp[i][k], dp[i+1][k])

for j in range(V-1, -1, -1):
  if dp[N][j] <= W:
    print(j)
    exit()
### BUGGY CODE ###

n,k = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]


t = [0]*(n-k+1)
tmp = 0
for i in range(n-k+1):
    for x in range(k):
        num = p[i+x]
        tmp += sum(range(num+1)) / num
    t[i] = tmp
    tmp = 0

print(max(t))

### FIXED CODE ###

n,k = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]


t = [0] * (n+k+1)
for i in range(n):
    t[i+1] = t[i] + p[i]

ans = 0
for i in range(n):
    ans = max(ans, t[i+k]-t[i])
print((ans+k)/2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


# 解説AC
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)


def check(mid):
    k = K
    # 全員が目標値 mid を下回るまで修行できるか？
    for i in range(N):
        if A[i] * F[i] > mid:
            # x: 必要な修行回数
            x = A[i] - mid // F[i]
            k -= x
            # 誰かが修行できなかった ⇒ その目標値は達成不可能
            if k < 0:
                return False
    return True


def main():
    H = []
    for i in range(N):
        H.append(A[i]*F[i])
    # lb := 条件を満たさない最大, ub := 条件を満たす最小
    lb, ub = -1, max(H)
    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid):
            ub = mid
        else:
            lb = mid
    print(ub)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


# 解説AC
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)


def check(mid):
    k = K
    # 全員が目標値 mid を下回るまで修行できるか？
    for i in range(N):
        if A[i] * F[i] > mid:
            # x: 必要な修行回数
            x = A[i] - mid // F[i]
            k -= x
            # 誰かが修行できなかった ⇒ その目標値は達成不可能
            if k < 0:
                return False
    return True


def main():
    H = []
    for i in range(N):
        H.append(A[i]*F[i])
    # lb := 条件を満たさない最大, ub := 条件を満たす最小
    lb, ub = -1, max(H)
    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid):
            ub = mid
        else:
            lb = mid
    print(ub)


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

from collections import deque

def main():
    n, adj = getInputs()

    # maxDistance[start]
    maxDistance = [0] * n
    calculated = set()

    for v in getVertexSequence(n, adj):
        # distance[dest] (starting at v)
        distance = [0] * n

        toVisit = deque([v])

        while len(toVisit) > 0:
            curr = toVisit.popleft()

            for dest in adj[curr]:
                if dest in calculated:
                    distance[dest] = max(
                        distance[dest],
                        distance[curr] + maxDistance[dest] + 1
                    )
                else:
                    if distance[curr] + 1 > distance[dest]:
                        distance[dest] = distance[curr] + 1

                    toVisit.append(dest)

        maxDistance[v] = max(distance)
        calculated.add(v)

    print(max(maxDistance))

def getInputs():
    n, m = map(lambda x: int(x), input().split())

    adj = []
    for i in range(n):
        adj.append([])

    for i in range(m):
        a, b = map(lambda x: int(x), input().split())
        adj[a - 1].append(b - 1)

    return n, adj

def getVertexSequence(n, adj):
    pairs = []
    for i in range(n):
        pairs.append((i, adj[i]))

    pairs.sort(key=(lambda x: len(x[1])))

    sequence = []
    for i in range(n):
        sequence.append(pairs[i][0])

    return sequence

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def main():
    n, m = [int(x) for x in input().split()]
    global dp
    dp = [-1]*n
    grafo = [[] for _ in range(n)]

    for _ in range(m):
        x, y = [int(x) for x in input().split()]
        x -= 1
        y -= 1

        grafo[x].append(y)

    resp = 0
    for u in range(n):
        resp = max(dfs(u, grafo), resp)

    print(resp)
        

def dfs(u, grafo):
    global dp

    if len(grafo[u]) == 0:
        dp[u] = 0
        return dp[u]

    if dp[u] != -1:
        return dp[u]


    for v in grafo[u]:
        dp[u] = max(dfs(v, grafo) + 1, dp[u])

    return dp[u]
        
main()
### BUGGY CODE ###

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
from collections import deque
def bfs(sy, sx, gy, gx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    return d[gy][gx]

ans = 0
for gy in range(h):
    for gx in range(w):
        for sy in range(h):
            for sx in range(w):
                ans = max(ans, bfs(gy, gx, sy, sx))
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

from collections import deque
import numpy as np
def bfs(sy, sx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        #if y == gy and x == gx:
            #break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    d = np.array(d)
    return np.max(d)

ans = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] != "#":  
              ans = max(ans, bfs(sy, sx))
print(ans)
### BUGGY CODE ###

a, b = map(int,input().split())

while a!=0 and b!=0:
    a,b = max(a,b),min(a,b)
    a %= b

ans = 1
for i in range(2, b+1):
    t = 0
    while b % i == 0:
        b //= i
        # print(b)
        t = 1
        if b==1:
            break
    ans += t
    if b==1:
        break
    
print(ans)

### FIXED CODE ###

a, b = map(int,input().split())

while a!=0 and b!=0:
    a,b = max(a,b),min(a,b)
    a %= b

# print(b)

bb = b

ans = 1
i = 2
end = int((b+1)**0.5)+2
while i < end:
    t = 0
    while b % i == 0:
        b //= i
        # print(b)
        t = 1
        end = int((b+1)**0.5)+2
        if b==1:
            break
    ans += t
    if b==1:
        break
    i += 1

if b != 1 and bb != 1:
    ans += 1
    
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import copy

def solve():
    INF = 10**8+1
    N, K = list(map(int, input().split(" ")))
    X = [0]
    X.extend(list(map(int, input().split(" "))))
    X.sort()
    
    def dfs(depth, i, Xs):
        if depth == K:
            return 0
        
        ret1, ret2 = INF, INF
        if i+1 < len(Xs):
            # 右に移動
            cost = abs(Xs[i] - Xs[i+1])
            tmpXs = copy.deepcopy(Xs)
            del tmpXs[i]
            ret1 = dfs(depth+1, i, tmpXs) + cost
        if i-1 >= 0:
            # 左に移動
            cost = abs(Xs[i] - Xs[i-1])
            tmpXs = copy.deepcopy(Xs)
            del tmpXs[i]
            ret2 = dfs(depth+1, i-1, tmpXs) + cost
        
        return min(ret1, ret2)

    # 0座標のインデックスは？
    for i in range(len(X)):
        if X[i] == 0:
            break
    ans = dfs(0, i, X)
    print(ans)


if __name__ == "__main__":
    solve()

### FIXED CODE ###

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

"""解説
https://www.youtube.com/watch?v=5O4k1n5Ejzw

区間を考える問題

-30 -10 0 10 20 50

・K = 3のとき、

0座標を必ず含める、ある連続するK個のロウソクについて考える

・-30 -10 0 10
・-10 0 10 20
・0 10 20 50

左端と右端に到達する最小値を求めていけばよくて、間のロウソクは無視してよい（必ず移動中に火をつけるので）

すべての場合について求めて、その中の最小値が答え
"""
def solve():
    N, K = list(map(int, input().split()))
    X = list(map(int, input().split()))
    if 0 in X:
        # 0座標にロウソクがあるなら、火をつけるロウソクをひとつ減らしてよい
        K -= 1
    else:
        X.append(0)
    X.sort()

    origin_i = X.index(0)
    left_i = max(origin_i-K, 0)

    INF = 10**12
    ans = INF
    while left_i <= origin_i:
        if left_i+K < len(X):
            tmp1 = abs(X[left_i]-0)*2 + abs(X[left_i+K]-0)
            tmp2 = abs(X[left_i]-0) + abs(X[left_i+K]-0)*2
        else:
            break
        ans = min(ans, tmp1, tmp2)
        left_i += 1
    print(ans)

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

N,K = map(int,input().split())
A = [0]
A += list(map(int,input().split()))

i = 1
pas = [i]
k = 1
while k <= K:
    if A[i] in pas:
        rps = pas.index(A[i]) # roop start index
        ans = A[i]
        break
    pas.append(A[i])
    ans = A[i]
    i = A[i]
    k += 1
    
if k >= K:
    print(ans)
else:
    rpnum = (K-rps)%(len(pas)-rps) # roop number
    print(pas[rps+rpnum])

### FIXED CODE ###

import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()
### BUGGY CODE ###

import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, ), cache=True)
def main(n):
    for s in range(1, n+1):
        ans = 0
        for i in range(1, 101):
            for j in range(1, 101):
                for k in range(1, 101):
                    if i*i + j*j + k*k + i*j + j*k + k*i == s:
                        ans += 1
        print(ans)
        ans = 0


n = int(read())
main(n)


### FIXED CODE ###

n = int(input())

ans = [0 for _ in range(10001)]

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            s = x*x + y*y + z*z + x*y + y*z + z*x
            if s <= 10000:
                ans[s] += 1

for i in range(1, n+1):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
n = int(input())
s = list(map(int,input().split()))
s1 = np.array(s)
t,r = np.array([]),np.array([])
o = 0
for i in range(n):
    if s[i] not in t:
        t = np.append(t,s[i])
        r = np.append(r,1)
    else:
        p = np.where(t == s[i])
        r[p] += 1

for i in range(len(t)):
    q = r[i] - t[i]
    if q >= 0:
        o += q
    else:
        o += r[i]

print(int(o))

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
t = {}
o = 0
for i in range(n):
    if s[i] not in t.keys():
        t[s[i]] = 1
    else:
        t[s[i]] += 1

for i,j in t.items():
    if i > j:
        o += j
    else:
        o += j - i

print(o)
### BUGGY CODE ###

import sys

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

bits = 1 << N

xmemo = [sys.maxsize]*(N*bits)
ymemo = [sys.maxsize]*(N*bits)

for b in range(bits):
  for i in range(N):
    xmemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b*N+i])
    ymemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b*N+i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b*N+j])
      ymemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b*N+j])
      
ans = [sys.maxsize]*(N+1)

pos = 3**N
for t in range(pos):
  l = []
  for _ in range(N):
    l.append(t%3)
    t //= 3
  xi = 0
  yi = 0
  cnt = 0
  for i in range(N):
    if l[i] == 0:
      xi += 1 << i
      cnt += 1
    elif l[i] == 1:
      yi += 1 << i
      cnt += 1
  tmp = 0
  for i in range(N):
    tmp += min(xmemo[xi*N+i], ymemo[N*yi+i])
  ans[cnt] = min(ans[cnt], tmp)
  
  
for i in range(N+1):
  print(ans[i])

### FIXED CODE ###

import sys

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

bits = 1 << N

xmemo = [sys.maxsize]*(N*bits)
ymemo = [sys.maxsize]*(N*bits)

for b in range(bits):
  for i in range(N):
    xmemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b*N+i])
    ymemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b*N+i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b*N+j])
      ymemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b*N+j])
      
ans = [sys.maxsize]*(N+1)

for b in range(bits):
  b_ = b
  cnt = bin(b_).count('1')
  while b_ >= 0:
    b_ &= b
    yi = b - b_
    tmp = 0
    for i in range(N):
      tmp += min(xmemo[b_*N+i], ymemo[yi*N+i])
    ans[cnt] = min(ans[cnt], tmp)
    b_ -= 1
  
for i in range(N+1):
  print(ans[i])
### BUGGY CODE ###

def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j]=min(d[i][j],d[i][k]+d[k][j])
	return d
n,m,l=map(int,input().split())
d=[[10**10 for _ in range(n)]for _ in range(n)]
for i in range(n):
	d[i][i]=0
for i in range(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=c
	d[b-1][a-1]=c
p=[[10**5 for _ in range(n)]for _ in range(n)]
d=warshall_floyd(d)
for i in range(n):
	for j in range(n):
		if d[i][j]<=l:
			p[i][j]=1
p=warshall_floyd(p)
q=int(input())
for i in range(q):
	s,t=map(int,input().split())
	if p[s-1][t-1]==10**5:
		print(-1)
		continue
	print(p[s-1][t-1]-1)



### FIXED CODE ###

def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j]=min(d[i][j],d[i][k]+d[k][j])
	return d
n,m,l=map(int,input().split())
d=[[10**10 for _ in range(n)]for _ in range(n)]
for i in range(n):
	d[i][i]=0
for i in range(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=c
	d[b-1][a-1]=c
p=[[10**5 for _ in range(n)]for _ in range(n)]
d=warshall_floyd(d)
for i in range(n):
	for j in range(n):
		if d[i][j]<=l:
			p[i][j]=1
p=warshall_floyd(p)
q=int(input())
for i in range(q):
	s,t=map(int,input().split())
	if p[s-1][t-1]==10**5:
		print(-1)
		continue
	print(p[s-1][t-1]-1)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
T = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
  L,R = map(int, input().split())
  for r in range(R-1,N):
    for l in range(L):
      T[l][r] += 1
ans = []
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][q-1])
print('\n'.join(map(str,ans)))


### FIXED CODE ###

N,M,Q = map(int,input().split())
T = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
  L,R = map(int, input().split())
  T[L][R] += 1
for l in range(1,N+1):
  for r in range(1,N+1):
    T[l][r] += T[l-1][r]+T[l][r-1]-T[l-1][r-1]
ans = []
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][p-1]+T[q][q]-T[p-1][q]-T[q][p-1])
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    s = input()
    dp = np.zeros((N+1,N+1),dtype=int)
    for i in range(N):
        for j in range(1,N):
            if s[i] == s[j]:
                dp[i+1][j+1] = min(dp[i][j]+1,j-i)
    
    print(np.max(dp))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    s = input()
    a,i,j = 0,0,1
    
    while j < N:
        if s[i:j] in s[j:]:
            a = max(a,j-i)
            j += 1
        else:
            i += 1
        if i == j:
            i += 1
            j += 2
            
    print(a)

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

# 初期入力
#棒を長さでソートし、長いものはわかるようにした。残り2本を選ぶことで、組み合わせを減らした
N = int(input())
L = list(map(int, input().split()))
L_sorted =sorted(L,reverse=True)

#3本選ぶ組み合わせ,1番長いものに対して、一番短い物2本から比較していくとダメなものが速く選べる
from itertools import combinations
count =0
for i in range(N-2): #一番長い
    for j in range(1,N-1):#一番短い
        for k in range(j+1,N-1+1):#真ん中
            if L_sorted[j*(-1)] + L_sorted[k*(-1)] <= L_sorted[i]:
            #    print(L_sorted[i],L_sorted[ k*(-1) ],L_sorted[ j*(-1) ] )
                count +=1
            else:
                break
# N本の中から3本選ぶ組み合わせ
from math import factorial
N_3_all =factorial(N) // (factorial(N - 3) * factorial(3))

kotae =N_3_all -count
print(kotae)

### FIXED CODE ###

import bisect

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

count  =0
L.sort()
for i in range(0, N - 1):
  for j in range(i + 1, N):
    index = bisect.bisect_left(L, L[i] + L[j]) #AC:約2.9秒
    count += max(0, index - j - 1)

"""
    失敗:回答は出るがTLE:ランダム配列1000本で約6.2秒
    index = bisect.bisect_left(L[j+1:],L[i] + L[j]) #TLEの原因?
    count += index
"""
print(count)
### BUGGY CODE ###

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

last_ok_postion = 0 
last_ok_value = P[0]
count = 1

for i in range(1,N):
    if last_ok_value >= P[i]:
        check = 0
        for j in range(last_ok_postion,i)[::-1]:
            if P[j] < P[i]:
                check = 1
                break
        if check == 0:
            count += 1
print(count)

### FIXED CODE ###

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

last_ok_postion = 0 
count = 1

for i in range(1,N):
    if P[last_ok_postion] >= P[i]:
        m = min(P[last_ok_postion:i])
        if m >= P[i]:
            count += 1
            last_ok_postion = i
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = a.copy()
ans = 0

for i in range(n):
  count = 1
  del b[i]
  for j in range(n-1):
    if a[i] % b[j] == 0:
      count = 0
      break
  ans += count
  count = 1
  b = a.copy()
  
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
kmax = sorted(a)[-1]
c = [0]*(kmax+1)

for i in range(n):
  c[a[i]] -= 1
  for j in range(a[i],(kmax+1),a[i]):
    c[j] += 2

ans=c.count(1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        quit()
    s = 2
else:
    s = 1

for i in range(s, N, 2):
    if A.count(i) != 2:
        print(0)
        quit()
print(2**(N//2)%(10**9+7))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

if N % 2 == 1:
    if A.count(0) != 1:
        print(0)
        quit()

c = {}
for e in A:
    if e == 0:
        continue
    if e in c.keys():
        c[e] += 1
    else:
        c[e] = 1
if all([x == 2 for x in c.values()]):
    print(2**(N//2)%(10**9+7))
else:
    print(0)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(str(input()))
prize = []
for  j in range(n):
    if not(s[j] in prize):
        prize.append(s[j])
print(len(prize))

### FIXED CODE ###

n = int(input())
s = set()
for i in range(n):
    prize = str(input())
    s.add(prize)
print(len(s))
### BUGGY CODE ###

n,k=map(int,input().split())
*p,=map(int,input().split())
px=[]
for i in p:
	s=(i*(i+1))/2
	s1=s/i
	px.append(s1)
ans=[sum(px[i:i+k]) for i in range(n-k+1)]
print(max(ans))  

### FIXED CODE ###

n,k=map(int,input().split())
*p,=map(int,input().split())
px=[(i+1)/2 for i in p]
px_sum=[0]
for j in range(len(px)):
	px_sum.append(px_sum[j]+px[j])
ans=0
for i in range(n-k+1):
	a=px_sum[i+k]-px_sum[i]
	ans=max(a,ans)
print(ans)