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

from bisect import bisect
from operator import itemgetter
inpl = lambda: list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        self.size = 2 ** (int.bit_length(N)+1)
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        while 1 <= i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)


N, M = inpl()
R, L, S = [], [], []
Q = []
for _ in range(N):
    l, r = inpl()
    Q.append((l, r, (r-l+1)))

Q = sorted(Q, key=itemgetter(2), reverse=True)
rabit = RABIT(M+1)

for i in range(1, M+1):
    while Q and Q[-1][2] < i:
        l, r, _ = Q.pop()
        rabit.add_range(l, r, 1)
    ans = len(Q)
    for j in range(i, M+1, i):
        ans += rabit.get_range(j, j)
    print(ans)


### FIXED CODE ###

from bisect import bisect
from operator import itemgetter

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        self.size = 2 ** (int.bit_length(N)+1)
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)


N, M = inpl()
R, L, S = [], [], []
Q = []
for _ in range(N):
    l, r = inpl()
    Q.append((l, r, (r-l+1)))

Q = sorted(Q, key=itemgetter(2), reverse=True)
rabit = RABIT(M+1)

Lmin = M
Rmax = 0
for i in range(1, M+1):
    while Q and Q[-1][2] < i:
        l, r, _ = Q.pop()
        rabit.add_range(l, r, 1)
        Lmin = min(Lmin, l)
        Rmax = max(Rmax, r)
    ans = len(Q)
    for j in range(-(-Lmin//i) * i, Rmax+1, i):
        ans += rabit.get_range(j, j)
    print(ans)
### BUGGY CODE ###

# bin/env/pypy3
import sys
import collections
import heapq
import math
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_f = {}
memo_c = {}
def combinations_count(n, r):
    return n*(n-1)//2
    s = str([n,r])
    if s in memo_c:
        return memo_c[s]
    if not n in memo_f: memo_f[n] = math.factorial(n)
    b = max(n - r,0)
    if not b in memo_f: memo_f[b] = math.factorial(b)
    if not r in memo_f: memo_f[r] = math.factorial(r)
    memo_c[s] = memo_f[n] // (memo_f[b] * memo_f[r])
    return memo_c[s]
for e in a:
    c[e] -= 1
    b = [combinations_count(v,2) for v in c.values() if v > 1]
    print(sum(b))
    c[e] += 1


### FIXED CODE ###

# bin/env/pypy3
import sys
import collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_e = {}
s = sum(v*(v-1)//2 for v in c.values() if v > 1)
for e in a:
    if not e in memo_e:
        #c[e] -= 1
        if 1 < c[e]:
            memo_e[e] = s - (c[e]*(c[e]-1)//2 - (c[e]-1)*(c[e]-2)//2)
        else:
            memo_e[e] = s
    print(memo_e[e])
### BUGGY CODE ###

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

def main():
    n,k = map(int, input().split())
    l = list(map(int, input().split()))
    out = 0

    for i in range(len(l)-(k-1)):
        result = 0
        for j in range(k):
            result += sum(range(l[i+j]+1))/l[i+j]

        if out < result:
            out = result

    print(out)

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    n,k = map(int, input().split())
    l = list(map(mean, input().split()))
    out = sum(l[:k])
    result = out

    for i in range(1, len(l)-(k-1)):
        result = result - l[i-1] + l[i+k-1]

        if out < result:
            out = result

    print(out)

def mean(x):
    x = int(x)
    return x * (x+1) / (2 * x)

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

import sys
import fractions

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


if __name__ == "__main__":
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            ans = fractions.gcd(a,b)
            cnt += 6*ans
            for c in range(b+1,K+1):
                if a !=b and b!=c:
                    cnt += 6*fractions.gcd(ans, c)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)

### FIXED CODE ###

import sys
import fractions

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


if __name__ == "__main__":
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    dict_ = {}
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            if '{}_{}'.format(a,b) in dict_:
                ans = dict_['{}_{}'.format(a,b)]
            else:
                ans = fractions.gcd(a,b)
                dict_['{}_{}'.format(a,b)] = ans
            cnt += 6*ans
            for c in range(b+1,K+1):
                if '{}_{}'.format(ans,c) in dict_:
                    _ans = dict_['{}_{}'.format(ans,c)]
                else:
                    _ans = fractions.gcd(ans, c)
                    dict_['{}_{}'.format(ans,c)] = _ans
                cnt += 6*_ans
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)
### BUGGY CODE ###

s = input()
K = int(input())

def calculate(s,k):
    length = len(s)

    objs = {}
    for i in range(1,length+1):
        for j in range(0,length +1 - i):
            objs.__setitem__(s[j:j+i],True)

    s = sorted(objs.keys())

    print(s[k-1])


calculate(s,K)

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)

s = input()
K = int(input())


def calculate(str, k):
    s = sorted(list(set(str)))
    criteron = s[:k]
    objs = {}
    for index, s in enumerate(str):
        if s in criteron:
            if len(str)+1 > index + 1 + k:
                made = index + 1 + k
            else:
                made = len(str)+1
            for i in range(index+1,made):
                objs.__setitem__(str[index:i],True)

    arr = sorted(objs.keys())

    print(arr[k-1])

calculate(s, K)
### BUGGY CODE ###

s=input()
t=input()
n=len(s)

for i in range(n):
    a=s[i]
    b=t[i]
    s=s.translate(str.maketrans({a:b,b:a}))
    
    
if(s==t):print("Yes")
else:print("No")

### FIXED CODE ###

s=input()
t=input()
n=len(s)



sl=list(s)

sl.sort()
sl=''.join(sl)

a=''
for i in range(n):
    if(sl[i]==a):continue
    a=sl[i]
    b=t[s.index(a)]
    s=s.translate(str.maketrans({a:b,b:a}))
    sl=sl.translate(str.maketrans({a:b,b:a}))
    

if(s==t):print("Yes")
else:print("No")
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n = int(input())
orga = list(map(int, input().split()))

if n==1:
    print(1)
    exit()
if len(set(orga)) == 1:
    print(0)
    exit()

import collections
c = collections.Counter(orga)
a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

aset=set(orga)

def m_div(n,aset):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i!=n and i in aset:
                return False
            if i != n // i:
                if (n//i != n) and (n//i in aset):
                    return False
    return True

ans=0
for num in a:
    if m_div(num,aset):
        ans+=1

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

if n==1:
    print(1)
    exit()

maxa=max(a)
dp=[0]*(maxa+100)
for num in a:
    for i in range(2,10**10):
        if num*i > (maxa+50):
            break
        dp[num*i]=1

import collections
c = collections.Counter(a)

aa=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        aa.append(num)

ans=0
for num in aa:
    if dp[num]==0:
        ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
listn = list(map(int,input().split()))

ans = 0
for i in range(1,n+1):
    if listn[i-1]==min(listn[:i]):
        ans+=1

print(ans)
    



### FIXED CODE ###

n = int(input())
listn = list(map(int,input().split()))

a = 10**6
ans = 0
for i in range(n):
    if listn[i] <= a:
        a = listn[i]
        ans += 1

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

from collections import deque
def main():
  h,w = map(int,input().split())
  ch,cw = map(lambda x:int(x)+1,input().split())
  dh,dw = map(lambda x:int(x)+1,input().split())
  s = [["#"]*(w+4) for _ in range(2)]+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4) for _ in range(2)]
  m1 = ((-1,0),(0,-1),(0,1),(1,0))
  m2 = [(i,j) for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
  a = deque([(ch,cw)])
  b = deque()
  i = 0
  while a:
    while a:
      ah,aw = a.popleft()
      b.append((ah,aw))
      s[ah][aw] = i
      for bh,bw in m1:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    while b:
      ah,aw = b.popleft()
      for bh,bw in m2:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    i += 1
  ans = s[dh][dw]
  print(ans if ans != "." else -1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
  h,w = map(int,input().split())
  ch,cw = map(lambda x:int(x)+1,input().split())
  dh,dw = map(lambda x:int(x)+1,input().split())
  s = [["#"]*(w+4) for _ in range(2)]+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4) for _ in range(2)]
  m1 = ((-1,0),(0,-1),(0,1),(1,0))
  m2 = [(i,j) for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
  a = deque([(ch,cw)])
  b = deque()
  i = 0
  while a:
    while a:
      ah,aw = a.popleft()
      if s[ah][aw]!=".":
        continue
      b.append((ah,aw))
      s[ah][aw] = i
      for bh,bw in m1:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    while b:
      ah,aw = b.popleft()
      for bh,bw in m2:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    i += 1
  ans = s[dh][dw]
  print(ans if ans != "." else -1)

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

N = int(input())
power = 1
for i in range(1,N+1):
    power *= i
ans = power % (10**9 + 7)
print(ans)

### FIXED CODE ###

N = int(input())
power = 1
for i in range(1,N+1):
    power *= i
    power %= 10**9 + 7
print(power)
### BUGGY CODE ###

def chmin(a, b):
    if a > b:
        return b
    else:
        return a
    
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数

# 無限大の値
f_inf = float('inf')
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
for i in range(1, n):
    for j in range(1,k+1):
        if i-j < 0 :
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
  
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数

# 無限大の値
f_inf = 10 ** 9 
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
for i in range(1, n):
    for j in range(1,k+1):
        if i-j < 0 :
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

N=int(input())
S=list(input())
import collections
c=collections.Counter(S)
if len(c)==3:
  
  u=1
  for i in c.values():
    u=u*i 
  for i in range(N-2):
    for j in range(i+1,N-1):
      if 2*j-i<=N-1:
      
        if set([S[i],S[j],S[2*j-i]])=={'B','R','G'} :
          u=u-1
  print(u)       
else:
  print(0)
     

### FIXED CODE ###

N=int(input())
S=list(input())
import collections
c=collections.Counter(S)
if len(c)==3:
  
  u=1
  for i in c.values():
    u=u*i 
  for i in range(N-2):
    for j in range(i+1,int((N-1+i)/2)+1):
      
        if set([S[i],S[j],S[2*j-i]])=={'B','R','G'} :
          u=u-1
  print(u)       
else:
  print(0)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    x = [list(map(int, input().split())) for _ in range(N)] 
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, W + 1):
            dpi = dp[i]
            dpim = dp[i-1]
            if x[i - 1][0] <= j:
                dpi[j] = max(dpim[j], dpim[j - x[i - 1][0]] + x[i - 1][1])
            else:
                dpi[j] = dpim[j]

    print(dp[-1][W])

if __name__ == "__main__":
    main()


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])
### BUGGY CODE ###

def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    # morau
    for i, a in enumerate(A):
        dp[i][0] = pow(2, i, MOD)
            
        for j in range(S+1):
            if j >= a:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                dp[i+1][j] += dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                

    print(dp[N][S])
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    # morau
    for i, a in enumerate(A):
        dp[i][0] = pow(2, i, MOD)
            
        for j in range(S+1):
            if j >= a:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                dp[i+1][j] += dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                

    print(dp[N][S])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np

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

# 自分より左にいるやつが、全員自分以上であるような要素の数
counter = 0
for i in range(N):
    if np.all(P[:i+1] >= P[i]):
        counter += 1
print(counter)

### FIXED CODE ###

import numpy as np

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

# 自分より左にいるやつが、全員自分以上であるような要素の数
counter = 0
lowest = P[0]
for i in range(N):
    if P[i] <= lowest:
        lowest = P[i]
        counter += 1

print(counter)
### BUGGY CODE ###

mod = 10 ** 9 + 7

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    if i not in A:
        if i == 1:
            dp[i] = dp[i - 1] % mod
        else:
            dp[i] = dp[i - 1] + dp[i - 2] % mod
print(dp[n] % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7

n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]
not_wet = [True] * (n + 1)
for a in A:
    not_wet[a] = False
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    if not_wet[i]:
        if i == 1:
            dp[i] = dp[i - 1] % mod
        else:
            dp[i] = dp[i - 1] + dp[i - 2] % mod
print(dp[n] % mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    D =[int(i) for i in input().split()]
    count = 0
    D.sort()
    D.reverse()
    #print(D)
    for j in range(100000):
        for i in range(N):
            if D[i] < j:
                if i == (N/2):
                    count+=1
                else:
                    break
    print(count)
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    D =[int(i) for i in input().split()]
    #count = 0
    D.sort()
    D.reverse()
    center = D[int(N/2)]
    print(D[int((N/2))-1]-center)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
plist = list(map(float, input().split()))
dp[1][0], dp[1][1] = 1 - plist[0], plist[0]
for i in range(1, n):
    p = plist[i]
    for j in range(i + 1):
        dp[i + 1][j] += dp[i][j] * (1 - p)
        dp[i + 1][j + 1] += dp[i][j] * p
print(sum(dp[-1][n // 2 + 1:]))

### FIXED CODE ###

n = int(input())
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
plist = list(map(float, input().split()))
dp[1][0], dp[1][1] = 1 - plist[0], plist[0]
for i in range(1, n):
    p = plist[i]
    for j in range(i + 1):
        dp[i + 1][j] += dp[i][j] * (1 - p)
        dp[i + 1][j + 1] += dp[i][j] * p
print(sum(dp[-1][n // 2 + 1:]))
### BUGGY CODE ###

n,m=map(int,input().split())
D=[list(map(int,input().split())) for i in range(m)]

I=set(i for i in range(1,n+1))

for i in range(m):
  I &= set(i for i in range(D[i][0],D[i][1]+1))
print(len(I))  

### FIXED CODE ###

n,m=map(int,input().split())
D=[list(map(int,input().split())) for i in range(m)]
maxI=n
minI=1
for i in range(m):
  maxI=min(maxI,D[i][1])
  minI=max(minI,D[i][0])
print(max(maxI-minI+1,0))
### BUGGY CODE ###

n = int(input())
s = input()

result = 10**10
for i in range(n):
    west_s = s[:i]
    east_s = s[(i+1):]
#    print(west_s)
#    print(east_s)
    
#    print(west_s.count("W"))
#    print(east_s.count("E"))
    
    if((west_s.count("W")+east_s.count("E")) < result):
        result = west_s.count("W")+east_s.count("E")

print(result)

### FIXED CODE ###

n = int(input())
s = input()


score = s[1:].count("E")
result = score

for i in range(1,n):
    if(s[i]=="E"):
        score -= 1
    if(s[i-1]=="W"):
        score += 1
    
    if(score < result):
        result = score

print(result)
### BUGGY CODE ###

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

A = list(map(int,input().split()))

B = [0]*41

for i in range(N):
    for j in range(41):
        if (A[i]>>j) & 1 == 1:
            B[j] += 1
    #print(B)

C = []
for i in range(K+1):
    X = 0
    for j in range(41):
        if (i>>j) & 1 == 1:
            X += (N-B[j])*2**j
        elif (i>>j) & 1 == 0 and B[j] != 0:
            X += B[j]*2**j
    C.append(X)
            

print(max(C))
    

### FIXED CODE ###

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

A = list(map(int,input().split()))

B = [0]*41

for i in range(N):
    for j in range(41):
        if (A[i]>>j) & 1 == 1:
            B[j] += 1
#print(B)

C = [0]*41
for i in range(41):
    if (K>>i) & 1 == 1:
        C[i] += 1
#print(C)
D =[]
for i in range(40,-1,-1):
    count = 0
    if C[i] == 1:
        count += B[i]*2**i
        for k in range(40,i,-1):
            if C[k] == 0:
                count += B[k]*2**k
            else:
                count += (N-B[k])*2**k
        for j in range(i):
            if N-B[j] >= B[j]:
                count += (N-B[j])*2**j
            else:
                count += B[j]*2**j
    D.append(count)
score = 0
for i in range(41):
    if C[i] == 0:
        score += B[i]*2**i
    else:
        score += (N-B[i])*2**i
D.append(score)
#print(D)
print(max(D))
### BUGGY CODE ###

import math
A,B,N = map(int, input().split())
d = [0]
x = 0
for i in range(N+1):
    C = math.floor(A*x/B)
    D = math.floor(x/B)
    if D != 0:
        break
    ans = C-A*D
    d.append(ans)
    x += 1
print(max(d))
    


### FIXED CODE ###

import math
A,B,N = map(int, input().split())
if (B-1)<=N:
    print(math.floor(A*(B-1)/B)-math.floor((B-1)/B)*A)
else:
    print(math.floor(A*N/B)-math.floor(N/B)*A)
### BUGGY CODE ###


N = int(raw_input())
A = [int(i) for i in raw_input().split()]

A0 = A[0:N:2]
A1 = A[1:N:2]

S0 = set(A0)
S1 = set(A1)
N0 = []
N1 = []

for s in S0:
    N0.append((s, sum(map(lambda x: x==s, A0))))

for s in S1:
    N1.append((s, sum(map(lambda x: x==s, A1))))

N0.sort(key=lambda x: x[1], reverse=True)
N1.sort(key=lambda x: x[1], reverse=True)

if N0[0][0] == N1[0][0]:
    if N0[0][0] < N1[0][0]:
        if len(N0) == 1:
            print N - N1[0][1]
        else:
            print N - N0[1][1] - N1[0][1]
    else:
        if len(N1) == 1:
            print N - N0[0][1]
        else:
            print N - N0[0][1] - N1[1][1]
else:
    print N - N0[0][1] - N1[0][1]


### FIXED CODE ###


from collections import Counter

n    = int(raw_input())
nums = list(map(int, raw_input().split()))

nums_odd  =   nums[0:n:2]
nums_even =   nums[1:n:2]

N_odd     =   sorted(Counter(nums_odd ).items(), key=lambda x: x[1], reverse=True) + [(-1,0)]
N_even    =   sorted(Counter(nums_even).items(), key=lambda x: x[1], reverse=True) + [(-1,0)]

if N_odd[0][0] == N_even[0][0]:
    if N_odd[0][1] + N_even[1][1] > N_odd[1][1] + N_even[0][1]:
        print n - N_odd[0][1] - N_even[1][1]
    else:
        print n - N_odd[1][1] - N_even[0][1]
else:
    print n - N_odd[0][1] - N_even[0][1]
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
exit = sys.exit


def main():
    N = int(input().strip())
    S = input().strip()
    half_N = N//2
    cand = []
    flag = True
    cappend = cand.append
    for i in range(N):
        tmp = []
        tappend = tmp.append
        for j in range(1, N-i-1):
            if S[i] == S[i+j]:
                flag = False
                tappend(i+j)
        cappend(tmp)
    if flag:
        print(0)
        exit()

    for length in range(1, N//2+1):
        flag = True
        new_cand = []
        ncappend = new_cand.append
        for i in range(N-length):
            tmp = []
            now_check = S[i+length]
            tappend = tmp.append
            for c in cand[i]:
                if i + length >= c or c + length >= N:
                    continue
                if S[c+length] == now_check:
                    flag = False
                    tappend(c)
            ncappend(tmp)
        cand = new_cand
        if flag:
            print(length)
            exit()

    print(length+1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()

    dp = [0] * N
    for i, s in enumerate(S):
        if i == 0:
            continue
        before_ans = dp[i-1]
        now_S = S[:i+1]
        tmp_ans = now_S[-(before_ans+1):i+1]
        # print(i, before_ans, tmp_ans)
        if tmp_ans in now_S[:-(before_ans+1)]:
            dp[i] = before_ans + 1
        else:
            dp[i] = before_ans
    print(dp[-1])


if __name__ == "__main__":
    main()