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

def main():
    from sys import stdin
    input = stdin.readline

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    for cnt in range(min(k, 41)):
        ans = []
        bit = [0]*(n+1)
        for i, j in enumerate(a):
            x, y = max(i-j, 0)+1, min(i+j+1, n)+1
            while x < n+1:
                bit[x] += 1
                x += x & (-x)
            while y < n+1:
                bit[y] -= 1
                y += y & (-y)
        for i in range(n):
            ret, x = 0, i+1
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            ans.append(ret)
        a = ans

    print(*ans)


main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    for cnt in range(min(k, 41)):
        ans = []
        bit = [0]*(n+1)
        for i, j in enumerate(a):
            x, y = max(i-j, 0)+1, min(i+j+1, n)+1
            while x < n+1:
                bit[x] += 1
                x += x & (-x)
            while y < n+1:
                bit[y] -= 1
                y += y & (-y)
        for i in range(n):
            ret, x = 0, i+1
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            ans.append(ret)
        a = ans

    print(*ans)


main()
### BUGGY CODE ###

N,M = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
ans = 0
tmp = 0
while tmp < M:
    num = min([M-tmp,B[A.index(min(A))]])
    tmp += num
    ans += num * min(A)
    ind = A.index(min(A))
    del A[ind]
    del B[ind]
print(ans)

### FIXED CODE ###

from operator import itemgetter
N,M = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(N)]
ls = sorted(ls,key=itemgetter(0))
ans = 0
pon = 0
for i in range(N):
    if pon < M:
        pon += ls[i][1]
        ans += ls[i][1]*ls[i][0]
    else:
        i = i-1
        break
if pon == M:
    print(ans)
else:
    ans -= ls[i][0]*(pon - M)
    print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())

if L - R >= 2019:
    ans = 0
else:
    ans = 2019
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            a = (i * j) % 2019
            ans = min(a, ans)

print(ans)


### FIXED CODE ###

import sys

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

yy = 2019

d = 2019

if R > L+2019:
    R = L+2019

for i in range(L,R):
    im = i % yy

    for j in range(i+1, R+1):
        jm = j % yy

        if im * jm % yy <= d:
            d = im * jm % yy

print(d)
### BUGGY CODE ###

s = list(input())
mod = 10**9+7
dp = [[0]*13 for i in range(len(s)+1)]
dp[0][0] = 1
ten = 1

s = s[::-1]
for i in range(len(s)):
    if s[i] == "?":
        for k in range(10):
            x = k*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] += dp[i][j]
    
    else:
        x = int(s[i])*ten%13
        for j in range(13):
            dp[i+1][(j+x)%13] += dp[i][j]%mod

    ten *= 10%mod

print(dp[-1][5]%mod)

### FIXED CODE ###

def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod
        
        else:
            x = int(s[i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod

        ten = (ten*10)%13

    print(dp[-1][5]%mod)

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

from heapq import heappop,heappush
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
lst=[]
for i in range(n):
    heappush(lst,[-b[i],i])
count=0
while lst:
    c=heappop(lst)
    num, j=c
    if -num==a[j]:
        continue
    if j==0:
        i=n-1
        k=1
    elif j==n-1:
        i=n-2
        k=0
    else:
        i=j-1
        k=j+1
    num*=(-1)
    if (num-a[j])%(b[i]+b[k])==0:
        count+=(num-a[j])//(b[i]+b[k])
        b[j]=a[j]
        continue
    if num//(b[i]+b[k])==0:
        print(-1)
        break
    count+=num//(b[i]+b[k])
    num%=(b[i]+b[k])
    if num>a[j]:
        heappush(lst,[-num, j])
        b[j]=num
    elif num==a[j]:
        b[j]=num
        continue
    else:
        print(-1)
        break
else:
    print(count)

### FIXED CODE ###

from heapq import heappush,heappop
import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
lst=[]
for i in range(N):
    heappush(lst,(-B[i],i))

count=0
while lst:
    h,i=heappop(lst)
    h=-h
    x,z=B[i-1],B[(i+1)%N]
    kkk=x+z
    if (h-A[i])%kkk==0:
        count+=(h-A[i])//kkk
        B[i]=A[i]
        continue
    elif kkk>=h:
        print(-1)
        sys.exit()
    else:
        count+=h//kkk
        h=h%kkk
        B[i]=h    
        if A[i]>h:
            print(-1)
            sys.exit()
        heappush(lst,(-h,i))

if A==B:
    print(count)
else:
    print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)


n = int(input())
a = list(map(int, input().split()))
g = [1] * n

ans = 1
for i in range(n):
    if i == 0:
        g[0] = a[1]
    else:
        g[0] = a[0]
    for j in range(1, n):
        if i == j:
            g[j] = g[j - 1]
            continue
        g[j] = gcd(g[j - 1], a[j])
    ans = max(ans, g[n - 1])

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)


n = int(input())
a = list(map(int, input().split()))
li = [0] * (n + 1)
r = [0] * (n + 1)

for i in range(n):
    li[i + 1] = gcd(li[i], a[i])

for i in range(n - 1, -1, -1):
    r[i] = gcd(r[i + 1], a[i])

ans = 0
for i in range(n):
    ans = max(ans, gcd(li[i], r[i + 1]))

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

n,W,*wv=map(int,open(0).read().split())
w=wv[::2]
v=wv[1::2]
dp=[[0 for i in range(W+1)]for j in range(n)]
for i in range(n):
  for j in range(W+1):
    if i==0:
      if j<w[i]:
        dp[i][j]=0
      else:
        dp[i][j]=v[i]
    else:
      if j<w[i]:
        dp[i][j]=dp[i-1][j]
      else:
        dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])
print(dp[-1][-1])

### FIXED CODE ###

import numpy as np
n,W,*wv=map(int,open(0).read().split())
w=np.array(wv[::2])
v=np.array(wv[1::2])
dp=np.zeros([n+1,W+1],dtype=int)
for i in range(1,n+1):
  now=np.zeros(W+1,dtype=int)
  now[w[i-1]:]=dp[i-1][:-w[i-1]]+v[i-1]
  dp[i]=np.maximum(dp[i-1],now)
print(dp[-1][-1])
### BUGGY CODE ###

n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=set()
for i in range(n-1):
    if(lista[i]==lista[i+1]):
        listde.add(lista[i])
t=0
for i in range(n):
    t=0
    for k in listde:
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        listde.add(lista[i])
print(s)
    
        


### FIXED CODE ###

n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
lista.sort()
listtf=[]
s=0
for i in range(lista[n-1]):
    listtf+=[True]
for i in range(n):
    
    if(listtf[lista[i]-1]):
        if(i<n-1 and lista[i]==lista[i+1]):
            s-=1
        s+=1
        t=1
        while(t*lista[i]<=lista[n-1]):
            listtf[lista[i]*t-1]=False
            t+=1
print(s)
### BUGGY CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    for i in range(len(S)):
        mod = int_S % (10**(i+1)) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)
### BUGGY CODE ###

n = int(raw_input())
ais = map(int, raw_input().split())
def gcd(a,b):
	return gcd(b, a % b ) if b else a
m = min(ais)
for a in ais:
	for b in ais:
		a,b = min(a,b), max(a,b)
		if b% a:
			m = min(m, gcd(a,b))
print m

#6 = 3 * 2 + 

### FIXED CODE ###

n = int(raw_input())
ais = map(int, raw_input().split())
def gcd(a,b):
	return gcd(b, a % b ) if b else a
print reduce(gcd, ais)
### BUGGY CODE ###

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

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

dp = [0] * N
for i in range(1, N):
    dp[i] = min(abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i))

print(dp[-1])


### FIXED CODE ###

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

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i))
    
    print(dp[-1])
main()
### BUGGY CODE ###

#%%
r, g, b, n = map(int, input().split())
ans = 0
for i in range(n//r+2):
    flag = False
    for j in range(n//g+2):
        tmp = n - (r*i + g*j)
        if j == 0 and tmp < 0:
            flag = True
        if tmp < 0:
            break 
        if tmp >= 0 and tmp % b == 0:
            ans += 1
    if flag:
        break


print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n//r+2):
    flag = False
    for j in range(n//g+2):
        tmp = n - (r*i + g*j)
        if tmp < 0:
            break 
        if tmp % b == 0:
            ans += 1

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

H, W, M = map(int, input().split())
bombs_h = [0] * H
bombs_w = [0] * W
S = [[] for _ in range(H)]
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    S[h].append(w)
    bombs_h[h] += 1
    bombs_w[w] += 1

max_h = max(bombs_h)
max_w = max(bombs_w)
hs = [i for i, x in enumerate(bombs_h) if x == max_h]
ws = [i for i, x in enumerate(bombs_w) if x == max_w]
p = 1
for i in hs:
    for j in ws:
        if j not in S[i]:
            p = 0
            break
ans = max_w + max_h - p
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
bombs_h = [0] * H
bombs_w = [0] * W
B = []
for _ in range(M):
    h, w = map(lambda x: int(x)-1, input().split())
    B.append((h, w))
    bombs_h[h] += 1
    bombs_w[w] += 1

max_h = max(bombs_h)
max_w = max(bombs_w)
hs = [i for i, x in enumerate(bombs_h) if x == max_h]
ws = [i for i, x in enumerate(bombs_w) if x == max_w]
k = len(hs)*len(ws)
cnt = 0
for h, w in B:
    if bombs_h[h] == max_h and bombs_w[w] == max_w:
        cnt += 1
ans = max_w + max_h - (cnt == k)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    heappush(heap, (0, s))
    while heap:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]:
            continue
        dist[v] = d
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V = list(range(1, n+1))
E1, E2 = {v: {} for v in V}, {v: {} for v in V}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E1[u][v] = a
    E1[v][u] = a
    E2[u][v] = b
    E2[v][u] = b
ans = [MON]*n
dist_yen = dijkstra(V, E1, s)
dist_snuuk = dijkstra(V, E2, t)
temp = float('inf')
for v in V[::-1]:
    temp = min(temp, dist_yen[v] + dist_snuuk[v])
    ans[v-1] -= temp
print(*ans, sep='\n')

### FIXED CODE ###

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V = list(range(1, n+1))
E1, E2 = {v: {} for v in V}, {v: {} for v in V}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E1[u][v] = a
    E1[v][u] = a
    E2[u][v] = b
    E2[v][u] = b
ans = [MON]*n
dist_yen = dijkstra(V, E1, s)
dist_snuuk = dijkstra(V, E2, t)
temp = float('inf')
for v in V[::-1]:
    temp = min(temp, dist_yen[v] + dist_snuuk[v])
    ans[v-1] -= temp
print(*ans, sep='\n')
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
# x = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
# n = int(input())
# n, m = list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
a.sort()
bc_sorted = sorted(bc, key=lambda x: x[1], reverse=True)
l = 0
for i in range(m):
    l += bc[i][0]
j = 0
for i in range(l):
    if a[0] <= bc_sorted[j][1]:
        a[0] = bc_sorted[j][1]
        bc_sorted[j][0] -= 1
        if bc_sorted[j][0] == 0:
            j += 1
    else:
        break
    a.sort()

print(sum(a))


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
# x = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
# n = int(input())
# n, m = list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
a.sort()
bc_sorted = sorted(bc, key=lambda x: x[1], reverse=True)
l = 0
for i in range(m):
    l += bc[i][0]
j = 0
for i in range(min(l, n)):
    if a[i] <= bc_sorted[j][1]:
        a[i] = bc_sorted[j][1]
        bc_sorted[j][0] -= 1
        if bc_sorted[j][0] == 0:
            j += 1
    else:
        break
print(sum(a))
### BUGGY CODE ###

# coding: utf-8

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

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


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

import bisect

N = int(input())
L = sorted([int(n) for n in input().split()])

triples = set()

for i in range(len(L)):
    for j in range(i):
        a = L[i]
        b = L[j]

        right_index = bisect.bisect_left(L, a + b)
        left_index = bisect.bisect_right(L, abs(a - b))
        
        for k in range(left_index, right_index):
            triple = frozenset([i,j,k])
            if len(triple) == 3:
                triples.add(frozenset([i,j,k]))

print(len(triples))

### FIXED CODE ###

import bisect

N = int(input())
L = [int(n) for n in input().split()]
L = sorted(L)

total = 0

for i in range(N - 2):
    a = L[i]
    for j in range(i + 1, N - 1):
        b = L[j]
        right_endpoint = bisect.bisect_left(L, a+b, j)
        total += right_endpoint - j - 1

print(total)
### BUGGY CODE ###

import collections
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]

Q1 = [[1, 1]]
Q2 = [[1, 1]]
for i in range(3):
    if A[i] < B[i]:
        Q1 += [[A[i], B[i]]]
    elif A[i] > B[i]:
        Q2 += [[A[i], B[i]]]
dp1 = collections.defaultdict(lambda: -float('inf'))
dp1[0] = 0
for i in range(N + 1):
    for xs in Q1:
        dp1[i] = max([dp1[i], dp1[i - xs[0]] + xs[1]])
dp2 = collections.defaultdict(lambda: -float('inf'))
dp2[0] = 0
M = dp1[N]
for i in range(M + 1):
    for xs in Q2:
        dp2[i] = max([dp2[i], dp2[i - xs[1]] + xs[0]])
print(dp2[M])


### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max(i, c0, c1, c2)
    return dp[n]


print(count(count(N, A, B), B, A))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
if a[0] > 0 or a.count(0) > 1:
  print(0)
  exit()
  
a = sorted(a)
dp = [0]*(n+1)
dp[0] = 1
count_list = [0]*n
count_list[0] = 1
for i in range(1, n):
  num = a[i]
  count_list[num] += 1
  dp[a[i]] = dp[num-1] * count_list[num-1] ** count_list[num] % 998244353
print(dp[a[n-1]])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if a[0] > 0 or a.count(0) > 1:
  print(0)
  exit()
  
a = sorted(a)
dp = [0]*(n+1)
dp[0] = 1
count_list = [0]*n
count_list[0] = 1
for i in range(1, n):
  count_list[a[i]] += 1
for i in range(1, a[n-1]+1):
  dp[i] = dp[i-1] * count_list[i-1] ** count_list[i] % 998244353
print(dp[a[n-1]])
### BUGGY CODE ###

A, B, K = map(int, input().split())

tmp_s = {i for i in range(A, A+K)}
tmp_l = {i for i in range(B+1-K, B+1)}
whole = {i for i in range(A, B+1)}

ans = list(tmp_s.union(tmp_l).intersection(whole))
ans.sort()

print(*ans, sep="\n")

### FIXED CODE ###

A, B, K = map(int, input().split())

tmp_s = {i for i in range(A, A+K)}
tmp_l = {i for i in range(B+1-K, B+1)}

ans = list(tmp_s.union(tmp_l))
ans = [i for i in ans if A<=i<=B]
ans.sort()

print(*ans, sep="\n")
### BUGGY CODE ###

s = input()
T = [0]
for i in range(len(s)):
    T.append(int(s[i::]))

T = [t % 2019 for t in T]
print(len(T)-len(set(T)))

### FIXED CODE ###

s = input()

MOD = 2019
d = [0] * MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1

print(sum(i * (i - 1) // 2 for i in d))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
# tmp = set()
# from bisect import bisect_left
# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#         break
#     tmp.add(v)
# #     na = []
# #     ii = bisect_left(a, v*2)
# #     for 
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

tmp = [a[0]]
ss = 0
for i in range(1, n):
    num = a[i]
    for j in range(len(tmp)):
        item = tmp[j]
        if num%item==0:
            break
        if item*2>num:
            ss = j
#             print(item, num, ss)
            tmp.append(num)
            break
    else:
        tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
for num in range(1, N+1):
  count = 0
  tmp = []
  for i in range(len(A)):
    if A[i] == num:
      count += 1
    else:
      tmp.append(A[i])
  A = tmp
  print(count)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
s=0
for num in range(1, N+1):
  count = 0
  for i in range(s, N-1):
    if A[i] == num:
      count += 1
    else:
      break
  s+=count
  print(count)
### BUGGY CODE ###

A, B, C, K = list(map(int, input().split( )))
max_score = 0

while(K != 0):
    if(A == 0 and B == 0 and C > 0):
        C -= 1
        max_score += -1
    if(A == 0 and B > 0):
        B -= 1
    if(A > 0):
        A -= 1
        max_score += 1
    K -= 1

print(max_score)

### FIXED CODE ###

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

if(K < A):
    score = K
elif(K >= A and K <= A+B):
    score = A
else:
    score = A - (K - A - B)

print(score)
### BUGGY CODE ###

def intersect_list(lst1, lst2):
    arr = []
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            pass
        else:
            arr.append(element)
    return len(arr)

n=int(input())
a=[input() for i in range(n)]
a=list(map(lambda x:list(x),a))
count=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if intersect_list(a[i],a[j])==len(a[i]):
            count+=1
print(count)

### FIXED CODE ###

import math
import collections

n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))
### BUGGY CODE ###

S = int(input())
x1, y1, x2, y2, x3, y3 = 0, 0, 0, 0, 0, 0

for i in range(1, int((S * 2) ** 0.5) + 1):
  if S * 2 % i == 0:
    tmp = S * 2 // i
    x2 = tmp // 2
    x3 = tmp - x2
    y3 = i
    if y3 <= 1000000000 and x2 <= 1000000000 and x3 <= 1000000000:
      break
print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))

### FIXED CODE ###

S = int(input())
MOD = 10 ** 9
x1, y1, x2, y2 = 0, 0, MOD, 1
y3 = S // MOD
if S % MOD != 0:
  y3 += 1
x3 = x2 * y3 - S

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
### BUGGY CODE ###

import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(dict)
    ans = 0
    for l in range(N//2, 0, -1):
        t = 0
        for i in range(l):
            t |= 1 << (26*(l-i-1) + ord(S[i])-97)
        d[l][t] = [0, l-1]
        for i in range(1, N-l+1):
            t ^= 1 << (26*(l-1) + ord(S[i-1])-97)
            t = t << 26
            t |= 1 << (ord(S[i+l-1])-97)

            if t not in d[l]:
                d[l][t] = [i, i+l-1]
            else:
                if i > d[l][t][1]:
                    return l
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1] == S[j-1] and dp[i-1][j-1] < (j-i):
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] == 0
    return ans

if __name__ == '__main__':
    print(main())