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

n,q = map(int,input().split())
s = input()
L = [0]*n
for i in range(n-1):
    if s[i:i+2] == "AC":
        L[i] = 1

for i in range(q):
    l,r = map(int,input().split())
    print(sum(L[l-1:r-1]))


### FIXED CODE ###

n,q = map(int,input().split())
s = input().replace("AC","aC")
L = [0]*n
cnt = 0
for i in range(1,n):
    if s[i-1] == "a":
        cnt += 1
    L[i]=cnt
        
for i in range(q):
    l,r = map(int,input().split())
    print(L[r-1] - L[l-1])
### BUGGY CODE ###

N, Q = [int(nq) for nq in input().split()]
S = input()
ANS = []
for q in range(Q):
    l, r = [int(lr) for lr in input().split()]
    ans = S[l-1:r].count("AC")
    ANS.append(ans)
    print(ANS[q])

### FIXED CODE ###

N, Q = [int(nq) for nq in input().split()]
S = input()
AC = []
for s in range(len(S)-1):
    if S[s:s+2] == "AC":
        AC.append(1)
    else:
        AC.append(0)
CS = [0]*len(AC)
CS[0] = AC[0]
for i in range(len(AC)-1):
    CS[i+1] = CS[i] + AC[i+1]
for q in range(Q):
    l, r = [int(lr) for lr in input().split()]
    if l == 1:
        print(CS[r-2])
    else:
        print(CS[r-2] - CS[l-2])
### BUGGY CODE ###

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

ExP = list(map(lambda x: (x+1)/2, P))
ans = 0
for i in range(n-k+1):
#    print(ExP[i: i+k])
    ans = max(ans, sum(ExP[i: i+k]))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
ExP = list(map(lambda x: (x+1)/2, P))
ans = 0
prev = 0

#for i = 0
now = sum(ExP[0: k])
#print(0, now)
ans = max(ans, now)
prev = now

for i in range(1, n-k+1):
    now = prev - ExP[i-1] + ExP[i+k-1]
#    print(i, now)
    ans = max(ans, now)
    prev = now
print(ans)
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(lambda x:(x+1)/2,p))
from itertools import accumulate
A =  [0] + list(accumulate(p))
M = 0
index = 0
for x in range(N - K +  1):
    M = max(M,sum(p[x: x  + K]))
print(M)


### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
p = list(map(lambda x:(x+1)/2,p))
from itertools import accumulate
A =  [0] + list(accumulate(p))
M = 0
index = 0
for x in range(N - K +  1):
    M = max(M,A[x + K] - A[x])
print(M)
### BUGGY CODE ###

HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = {}
H = {}
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    if not h in H:
        H[h] = 1
    else:
        H[h] += 1
    
    if not w in W:
        W[w] = 1
    else:
        W[w] += 1

    HW[h][w] = 1
answer = 0
for ki, vi in H.items():
    for kj, vj in W.items():
        answer = max(answer,vi + vj - HW[ki][kj])

print(answer)
    

### FIXED CODE ###

import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = {}
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[(h,w)] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if not (h,w) in HW:
            print(answer)
            sys.exit(0)
print(answer-1)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A.sort()
B.sort()
C.sort()

import bisect
ans = 0

B_list = []
for b in B:
    B_list.append(bisect.bisect_left(A,b))

for c in C:
    b_bisect = bisect.bisect_left(B, c)
    for i, b in enumerate(B[:b_bisect]):
        #a_bisect = bisect.bisect_left(A,b)
        #の代わり
        a_bisect = B_list[i]
        ans += a_bisect 
print(ans)

### FIXED CODE ###

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


A.sort()
B.sort()
C.sort()

import bisect
ans = 0

a2b = []
c2b = []
for b in B:
    i = N - bisect.bisect_right(C, b)

    #例えば，C＝「13344」のとき，b=3とする，n=5なので，2になってほしい
    #bisect.bisect_right(C, b)＝3になるので，c＿bisect＝N-bisect.bisect_right(B, c)

    #例えば，C＝「133344」のとき，b=3とする，n=6なので，2になってほしい
    #bisect.bisect_right(C, b)＝4になるので，c＿bisect＝N-bisect.bisect_right(B, c)=2
    
    j = bisect.bisect_left(A, b)
    #例えば，A＝「13344」のとき，b=3とする，n=5なので，1になってほしい
    #bisect.bisect_left(A, b)＝1になるので，c＿bisect＝bisect.bisect_left(A, b)
    
    
    #例えば，A＝「113344」のとき，b=3とする，n=6なので，2になってほしい
    #bisect.bisect_left(A, b)＝2になるので，c＿bisect＝bisect.bisect_left(A, b)
    ans += i*j
    #print(i,j,i*j)
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
xyi = []
x = np.zeros(N)
y = np.zeros(N)

ans = 0
for i in range(N):
  x[i],y[i] = map(int, input().split())
  if i >0 :
    x_temp = np.abs(x[i] - x[:i])
    y_temp = np.abs(y[i] - y[:i])
    xy_temp = x_temp + y_temp
    temp = np.max(xy_temp)
    if temp > ans:
      ans = temp
  
  
print(int(ans))

### FIXED CODE ###

N = int(input())
z =[]
w = []
for i in range(N):
  x,y = map(int, input().split())
  z.append(x+y)
  w.append(x-y)
print(max(max(z)-min(z),max(w)-min(w)))
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

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

def mycomb(a, b) :
    return int(cmb(a, b))%dekai

def usless(tukau, i) :
    if tukau-i+1 < 0 :
        return 0
    else :
        return mycomb(k-1, i-1)*mycomb(tukau-1,i-2)

def sousa(i) :
    if i == 1 :
        return n-k+1
    else :
        wa = 0
        for utan in range(n-k+1) :
            for satan in range(n-k+1-utan) :
                tukau = n-k-utan-satan
                wa += usless(tukau, i)
        return wa%dekai

for ii in range(k) :
    print(sousa(ii+1))

### FIXED CODE ###

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


def comb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


for i in range(k) :
    ans = comb(n-k+1, i+1)*comb(k-1, i)%mod
    print(ans)
### BUGGY CODE ###

s = input()
t = input()
count = 0
sList = list(s)
tList = list(t)

for i in range(len(sList)):
    if sList == tList:
        break
    if sList[i] != tList[i]:
        sList[i] = tList[i]
        count = count + 1

print(count)



### FIXED CODE ###

s = input()
t = input()
count = 0
sList = list(s)
tList = list(t)

for i in range(len(s)):
    if s[i] != t[i]:
        count = count + 1

print(count)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9901
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc044/tasks/arc060_b

f(b,n)ってbが大きくなるほど大きくなる？(単調増加になる?)
→そんなことはない
nより大きかったら不可能。最小はn進法で桁和1

3桁以上になる物は全探索する
2桁は、良い感じにすべて調べ上げる
実装だるそ～

2桁の時 xyとなるとする
n//b = x
n%b  = y

n = bx+y
x+y = s

(n-S)//x+1 = b
かつ S >= x >= S-b

xについてn-sの約数を全列挙して、bを求める & 下の条件を満たしているか確認すればよい？
"""

def f(b,n):

    if n < b:
        return n
    else:
        return f(b,n//b) + (n%b)

import sys
n = int(input())
s = int(input())

if s > n:
    print (-1)
    sys.exit()
elif s == n:
    print (n+1)
    sys.exit()

for b in range(2,int(n**0.5+10)):

    if f(b,n) == s:
        print (b)
        sys.exit()

#ここからだるいパート
ans = float("inf")

for x1 in range(1,s+1):

    if (n-s) % x1 == 0:

        x2 = (n-s)//x1

        b1 = (n-s)//x1+1
        if b1 ** 2 > n and s >= x1 >= s-b1:
            ans = min(ans , b1)

        b2 = (n-s)//x2+1
        if b2 **2 > n and s >= x2 >= s-b2:
            ans = min(ans , b2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)


### FIXED CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc044/tasks/arc060_b

f(b,n)ってbが大きくなるほど大きくなる？(単調増加になる?)
→そんなことはない
nより大きかったら不可能。最小はn進法で桁和1

3桁以上になる物は全探索する
2桁は、良い感じにすべて調べ上げる
実装だるそ～

2桁の時 xyとなるとする
n//b = x
n%b  = y

n = bx+y
x+y = s

(n-S)//x+1 = b
かつ S >= x >= S-b

xについてn-sの約数を全列挙して、bを求める & 下の条件を満たしているか確認すればよい？
上の条件を満たしているbが必ずしも元の条件を満たすわけではなさそう？
ちゃんと満たしているか確認してあげる
"""

def f(b,n):

    if n < b:
        return n
    else:
        return f(b,n//b) + (n%b)

import sys
n = int(input())
s = int(input())

if s > n:
    print (-1)
    sys.exit()
elif s == n:
    print (n+1)
    sys.exit()

for b in range(2,int(n**0.5+10)):

    if f(b,n) == s:
        print (b)
        sys.exit()

#ここからだるいパート
ans = float("inf")

for x1 in range(1,10**6):

    if (n-s) % x1 == 0:

        x2 = (n-s)//x1

        b1 = (n-s)//x1+1
        if b1 ** 2 > n and s >= x1 >= s-b1 and f(b1,n) == s:
            ans = min(ans , b1)

        b2 = (n-s)//x2+1
        if b2 **2 > n and s >= x2 >= s-b2 and f(b2,n) == s:
            ans = min(ans , b2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
def print_ans(N, M, input_line):
    """Test Case
    >>> print_ans(3, 3, "2 13 8")
    9
    >>> print_ans(4, 4, "1 9 3 5")
    6
    >>> print_ans(1, 100000, "1000000000")
    0
    >>> print_ans(10 ,1, "1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000")
    9500000000
    """
    ar = np.array(list(map(float, input_line.split())))
    for _ in range(M):
        max_tmp_arg = np.argmax(ar)
        ar[max_tmp_arg] = ar[max_tmp_arg] // 2
    print(int(np.sum(ar)))

if __name__ == '__main__':
    N, M = map(int, input().rstrip().split())
    input_line = input().rstrip()
    print_ans(N, M, input_line)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq as hq
def print_ans(N, M, input_line):
    """Test Case
    >>> print_ans(3, 3, "2 13 8")
    9
    >>> print_ans(4, 4, "1 9 3 5")
    6
    >>> print_ans(1, 100000, "1000000000")
    0
    >>> print_ans(10 ,1, "1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000")
    9500000000
    """
    ar = [-int(i) for i in input_line.split()]
    hq.heapify(ar)
    for _ in range(M):
        hq.heappush(ar, -(-hq.heappop(ar) // 2))
    
    print(-sum(ar))

if __name__ == '__main__':
    N, M = map(int, input().rstrip().split())
    input_line = input().rstrip()
    print_ans(N, M, input_line)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)
max_idx = [i for i, x in enumerate(a) if x==a_max]

for i in range(n):
    if i in max_idx:
        copy = a[:]
        copy.pop(i)
        print(max(copy))
    else:
        print(a_max)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)
idx = [i for i, x in enumerate(a) if x==a_max]

if len(idx) > 1:
    for i in range(n):
        print(a_max)
else:
    for i in range(n):
        if a[i] == a_max:
            print(max(a[0:i]+a[i+1:]))
        else:
            print(a_max)
### BUGGY CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for n in range(N)]
P = []

for n in range(1, N + 1):
    P.extend(itertools.combinations([n for n in range(N)], n))

add_len = {s: sum(L[i] for i in s) for s in P}


def cost(v, s):
    return 10 * (len(s) - 1) + abs(v - add_len[s])


res = 2 << 30
for a in P:
    for b in P:
        if len(set(a) & set(b)):
            continue
        for c in P:
            if len(set(a) & set(c)) + len(set(b) & set(c)):
                continue
            res = min(res, cost(A, a) + cost(B, b) + cost(C, c))

print(res)


### FIXED CODE ###

import itertools

N, A, B, C = map(int, input().split())
L = [int(input()) for n in range(N)]
P = []

for n in range(1, N + 1):
    P.extend(itertools.combinations([n for n in range(N)], n))

add_len = {s: sum(L[i] for i in s) for s in P}


def cost(v, s):
    return 10 * (len(s) - 1) + abs(v - add_len[s])


res = 2 << 30
for a in P:
    cost_a = cost(A, a)
    if res < cost_a:
        continue

    for b in P:
        cost_b = cost(B, b)
        if res < cost_b:
            continue

        set_a = set(a)
        set_b = set(b)
        if len(set_a & set_b):
            continue

        for c in P:
            cost_c = cost(C, c)
            if res < cost_c:
                continue

            set_c = set(c)
            if len(set_a & set_c) or len(set_b & set_c):
                continue
            res = min(res, cost_a + cost_b + cost_c)

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

def f(a, num):
  if a[0]>=num:
    a=[num]+a
    return a
  if a[-1]<num:
    a[-1]=num
    return a
  x=0
  y=len(a)
  while y-x>1:
    z=(x+y)//2
    if a[z]>=num:
      y=z
    else:
      x=z
  a=a[:x]+[num]+a[y:]
  return a
      
  
N=int(input())
a=[int(input())]
for _ in range(N-1):
  a=f(a, int(input()))
print(len(a))

### FIXED CODE ###

import bisect
from collections import deque
N=int(input())
a=deque([int(input())])
for _ in range(N-1):
  num=int(input())
  if num<=a[0]:
    a.appendleft(num)
  else:
    a[bisect.bisect_left(a, num)-1]=num
print(len(a))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""
L,N = map(int, input().split(' '))
X = [int(input()) for i in range(N) ]

Xr = [0] + X

Yr = ["d"]
for i in range(0,N):
    Yr.append( Xr[i+1] - Xr[i])

Yl = ["d"]+[L-X[N-1]]
Yl += Yr[::-1]

S = []

answer = 0
for itr in range(1,N+1):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yr[counter]
        counter += 1
        
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yl[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yr[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
#    print(sum)
#    S.append(sum)
    answer = max(answer,sum)

for itr in range(1,N+1):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yl[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yr[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yl[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)
print(answer)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""
L,N = map(int, input().split(' '))
X = [int(input()) for i in range(N) ]

#inp = input().split()
#inp = [int(i) for i in inp]
#L, N = inp[0],inp[1]
#X = inp[2:]

X = [0] + X 
temp = L - X[1]
ans =  temp

itr1 = 0
itr2 = N

a = N%2

for i in range(-(N-1),N):
    if (i+a)%2 == 1:
        itr1 += 1
    else:
        itr2 -= 1

    if X[i]-X[i-itr1] >=0:
        minus = X[i]-X[i-itr1]
    else:
        minus = L+(X[i]-X[i-itr1])

    if X[i+itr2]-X[i] >=0:
        plus = X[i+itr2]-X[i]
    else:
        plus = L+(X[i+itr2]-X[i])
    temp = temp - minus + plus
#    print(temp)
    ans = max(ans,temp)
print(ans)
### BUGGY CODE ###

n = int(input())
inf = 10**9+7
a = list(int(x) for x in input().split())
b = []
for key in a:
    p = 0
    while key:
        q = key%2
        if q:
            if p >= len(b):
                b.append(1)
            else:
                b[p] = b[p]+1
        else:
            if p >= len(b):
                b.append(0)
        key = key//2
        p += 1
ans = 0
k = 1
q = 0
for key in b:
    if b[q]:
        ans = (ans+k*(n-b[q])*b[q])%inf
    q += 1
    k *= 2
print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array([int(x) for x in input().split()])
inf = 10**9+7

ans = 0
p = 1
for i in range(61):
    a, b = a//2, a%2
    key = int(b.sum())
    ans += p*(n-key)*key
    ans = ans%inf
    p *= 2
    p %= inf
print(ans)
### BUGGY CODE ###

import sys
n = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
res = 1
for i in range(n):
    res *= li[i]
print(res) if res <= 10**18 else print(-1)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))
if 0 in li:
    print(0)
    exit()
res = 1
for i in range(n):
    res *= li[i]
    if res > 1000000000000000000:
        print(-1)
        exit(0)
print(res)
### BUGGY CODE ###

a,b,c = map(int,input().split())
count = 0
for i in range(a,b+1):
  if i % c ==0:
    count += 1
  else:
    count +=0
print(count)


### FIXED CODE ###

a,b,c = map(int,input().split())
print(b // c - (a - 1) // c)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
goukei = 0
ind = 0
kitai = 0

for i in range(k):
    goukei = goukei + p[i]

list = [goukei]

for j in range(1, n-k+1):
    list.append(list[j-1] - p[j-1] + p[j+k-1])

ind = list.index(max(list))

for j in range(ind, ind+k):
    for i in range(1,p[j]+1):
        kitai = kitai + i/p[j]
'''
print(max(list))
print(p)
print(list)
print(ind)
'''
print(kitai)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split())) # list()でリスト化、それを変数に代入。
goukei = 0
ind = 0
kitai = 0

for i in range(k):
    goukei = goukei + p[i]

list = [goukei]

for j in range(1, n-k+1):
    list.append(list[j-1] - p[j-1] + p[j+k-1])

ind = list.index(max(list))

for j in range(ind, ind+k):
    kitai = kitai + (p[j]+1)/2
'''
print(max(list))
print(p)
print(list)
print(ind)
'''
print(kitai)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n = ni()
s = ns()

lenstr = []
dic = defaultdict(list)

for st in range(n):
    for ed in range(st+1, min(st+n//2+2, n+1)):
        lenstr.append((ed-st, s[st:ed]))
        dic[s[st:ed]].append(st)

ans = 0

for leni, stri in lenstr:
    if dic[stri][-1] - dic[stri][0] >= leni:
        ans = max(ans, leni)

print(ans)


### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class RollingHash(object):
    def __init__(self, source: str, base=10**9+7, mod=(1<<64)-1):
        self.source = source
        self.base = base
        self.mod = mod
        self.hash_from_zero_to = self._get_hash_from_zero_to()
        self.base_pow = self._get_base_pow()

    # 文字列sourceの区間 [0, right) のハッシュ値を前計算する
    def _get_hash_from_zero_to(self):
        hash_from_zero_to = [0]
        for si in self.source:
            hash_from_zero_to.append((hash_from_zero_to[-1] * self.base + ord(si)) % self.mod)

        return hash_from_zero_to

    # base値をi回掛けてmodをとった値を前計算する
    def _get_base_pow(self):
        base_pow = [1]
        for i in range(len(self.source)):
            base_pow.append(base_pow[-1] * self.base % self.mod)

        return base_pow

    # 文字列sourceの区間 [left, right) のハッシュを取得する
    def get_hash(self, left: int, right: int):
        return (self.hash_from_zero_to[right]
                - self.hash_from_zero_to[left] * self.base_pow[right - left]) % self.mod


def binsearch(func, rh: RollingHash, ok: int, ng: int):
    source_length = len(rh.source)
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if func(rh, mid, source_length):
            ok = mid
        else:
            ng = mid

    return ok


# 題意を満たす長さtarget_lengthの文字列があるか判定
def judge(rh: RollingHash, target_length: int, source_length: int):
    memo = {}
    for start_idx in range(source_length - target_length + 1):
        cur_hash = rh.get_hash(start_idx, start_idx + target_length)
        if cur_hash in memo:
            if start_idx - memo[cur_hash] >= target_length:
                return True
        else:
            memo[cur_hash] = start_idx

    return False


n = ni()
s = ns()

rh = RollingHash(s)
print(binsearch(judge, rh, 0, n//2 + 2))