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

# 自然数m以下の素数を返す（SETでRETURN）
import math
def prime_numbers(m):
    # 素数を保持するset
    primes = []

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.append(n)
        n += 1
    return primes

#素数で割れるか、同じ素数で何回割れるかは見てないから素因数分解とは違う（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            if i >m:
                break
            elif mm %i==0:
                pf.add(i)
                mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import sys
from collections import Counter
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
pri_num =prime_numbers(sq_pri +10 )

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    for a in A:
        aa =soinsu_bunkai(a)
        if intersect & aa:
            pair_w.add(0)
            break #共通要素があったらpair_wではない→set_w
        else:
            pair_w.add(1)
        intersect |=aa

    if 0 in pair_w:
        ans ="setwise coprime"        
    else:
        ans ="pairwise coprime"
print(ans)

### FIXED CODE ###

#高速素因数分解  osa_k法 
def osa_k(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
used =set()

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    MAXN =10**6 +10
    #osa_k法
    sieve = [i for i in range(MAXN+1)]
    p = 2
    while p*p <= MAXN:
        if sieve[p] == p:
            for q in range(2*p,MAXN+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1
    
    ans ="pairwise coprime"
    for a in A:
        aa =osa_k(a)
        if used & aa:
            ans ="setwise coprime"
            break #共通要素があったらpair_wではない→set_w
        used |=aa
    
print(ans)
### BUGGY CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,m,l = ma()
INF=10**15
cost = [[-1]*n for i in range(n)]
tree = [[] for i in range(n)]
for i in range(m):
    a,b,c = ma();a-=1;b-=1
    tree[a].append((c,b))
    tree[b].append((c,a))

def Dijkstra(graph,s):
    heap = [(0,l,s)] #スタートから距離が近い順に訪問
    rest = [INF]*n
    rest[s]=0
    while heap:
        cost,fuel,node = hq.heappop(heap)
        if cost>rest[node]:continue
        for w,nex in graph[node]:
            if fuel>=w:
                rest[nex]=min(cost,rest[nex])
                hq.heappush(heap,(cost,fuel-w,nex))
            else:
                if l<w:
                    pass
                else:
                    rest[nex]=min(cost+1,rest[nex])
                    hq.heappush(heap,(cost+1,l-w,nex))
    #print(s,rest)
    return rest
q = ni()
for i in range(q):
    s,t = ma();s-=1;t-=1
    if s>t:s,t=t,s
    if cost[s][t]==-1:
        cost[s] = Dijkstra(tree,s)

    print(cost[s][t]) if cost[s][t] !=INF else print(-1)


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,m,l = ma()
INF=10**15
cost = [[INF]*n for i in range(n)]
for i in range(m):
    a,b,c = ma();a-=1;b-=1
    cost[a][b]=c
    cost[b][a]=c

def wf(cost):
    l = len(cost[0])
    for k in range(l):
        for i in range(l):
            for j in range(l):
                cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
wf(cost)
rest = [[INF]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if cost[i][j]<=l:
            rest[i][j]=1
wf(rest)
q = ni()
for i in range(q):
    s,t = ma();s-=1;t-=1
    print(rest[s][t] -1) if rest[s][t] !=INF else print(-1)
### BUGGY CODE ###

# coding: utf-8

import sys
input=sys.stdin.readline

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

if n<=k:
    print(0)
else:
    for _ in range(k):
        h.remove(max(h))
    print(sum(h))

### FIXED CODE ###

# coding: utf-8

import sys
input=sys.stdin.readline

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

if n<=k:
    print(0)
else:
    h.sort()
    print(sum(h[:len(h)-k]))
### BUGGY CODE ###

def prime(n):
    num=[i for i in range(n,1,-1)]
    prime=[]
    p = 2
    while p <=n**0.5 or num:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0]
    return prime

def main():
    a,b=map(int,input().split(' '))
    prime_list=prime(min(a,b))
    ans = 1
    for i in prime_list:
        if a%i == 0 and b%i==0:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import *
def gcd(n,m):
    while m != 0:
        n,m=m,n%m
    return n
def main():
    a,b=map(int,input().split(' '))
    g=gcd(a,b)
    cnt = 1
    g2 = int(sqrt(g))
    for i in range(2,g2+1):
        if g%i ==0:
            while g%i ==0:
                g //= i
            cnt += 1
    if g > 1:
        cnt += 1
    print(cnt)

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

n = int(input())
a_list = [i for i in input().split()]

for i in range(n):
    print("{}".format(a_list.count(str(i+1))))

### FIXED CODE ###

n = int(input())
a_list = [int(i) for i in input().split()]
nl = [0 for i in range(n)]
for a in a_list:
    nl[a-1] += 1
for i in nl:
    print("{}".format(i))
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353

Pre = [[[] for _ in range(S+1)] for _ in range(N+1)]

Pre[0][0].append(0)

for i, a in enumerate(A):
    for j in range(S+1):
        Pre[i + 1][j] += Pre[i][j]
        if a + j <= S:
            for p in Pre[i][j]:
                Pre[i + 1][j + a].append(p + 1)
ans = 0
for L in Pre[N][S]:
    ans += pow(2, N - L, mod)
    ans %= mod

print(ans % mod)

### FIXED CODE ###

import numpy as np

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
f = np.zeros(3100, np.int64)

ans = 0
f[0] = 1
for a in A:
    g = f.copy()
    f[a:] += g[:-a]
    f += g
    f %= mod

print(f[S])
### BUGGY CODE ###

N, W = map(int, input().split())
wlist = [0] * N
vlist = [0] * N
for i in range(N):
	wlist[i], vlist[i] = map(int, input().split())
minw = min(wlist)
w = list()
for i in range(4):
	w.append(list())
for i in range(N):
	w[wlist[i] - minw].append(vlist[i])
for i in range(4):
	w[i].sort(reverse = True)
ans = 0
for i in range(len(w[0]) + 1):
	for j in range(len(w[1]) + 1):
		for k in range(len(w[2]) + 1):
			for l in range(len(w[3]) + 1):
				sumw = 0
				sumv = 0
				for z in range(i):
					sumw += minw
					sumv += w[0][z]
				for z in range(j):
					sumw += minw + 1
					sumv += w[1][z]
				for z in range(k):
					sumw += minw + 2
					sumv += w[2][z]
				for z in range(l):
					sumw += minw + 3
					sumv += w[3][z]
				if sumw <= W:
					ans = max(ans, sumv)
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
wlist = [0] * N
vlist = [0] * N
for i in range(N):
	wlist[i], vlist[i] = map(int, input().split())
minw = min(wlist)
w = list()
for i in range(4):
	w.append(list())
for i in range(N):
	w[wlist[i] - minw].append(vlist[i])
for i in range(4):
	w[i].sort(reverse = True)
ans = 0
sumw0 = 0
sumv0 = 0
for i in range(len(w[0]) + 1):
	sumw1 = 0
	sumv1 = 0
	for j in range(len(w[1]) + 1):
		sumw2 = 0
		sumv2 = 0
		for k in range(len(w[2]) + 1):
			sumw3 = 0
			sumv3 = 0
			for l in range(len(w[3]) + 1):
				sumw = sumw0 + sumw1 + sumw2 + sumw3
				sumv = sumv0 + sumv1 + sumv2 + sumv3
				if sumw <= W:
					ans = max(ans, sumv)
				if l != len(w[3]):
					sumw3 += minw + 3
					sumv3 += w[3][l]
			if k != len(w[2]):
				sumw2 += minw + 2
				sumv2 += w[2][k]
		if j != len(w[1]):
			sumw1 += minw + 1
			sumv1 += w[1][j]
	if i != len(w[0]):
		sumw0 += minw
		sumv0 += w[0][i]
print(ans)
### BUGGY CODE ###

n = int(input())
alist = list(map(int,input().split(' ')))

from collections import defaultdict

resdict = {}

from collections import Counter

c = Counter(alist)

old_cdict = dict(c)

cdict = dict((key, value) for (key, value) in old_cdict.items() if value >= 2)

# print(cdict)

maxi = 0

for k, v in cdict.items():
    maxi += v * (v - 1) // 2

for a in alist:
    if a in resdict:
        # print('used')
        print(resdict[a])
        continue
    # print('not used')
    if a in cdict:
        cdict[a] -= 1
        temp = 0
        for k,v in cdict.items():
            temp += v*(v-1)//2
        print(temp)
        resdict[a] = temp
        cdict[a] += 1
    else:
        print(maxi)

### FIXED CODE ###

n = int(input())
alist = list(map(int,input().split(' ')))

from collections import defaultdict

resdict = {}

from collections import Counter

c = Counter(alist)

cdict = dict(c)

# cdict = dict((key, value) for (key, value) in old_cdict.items() if value >= 2)

# print(cdict)

maxi = 0

for k, v in cdict.items():
    maxi += v * (v - 1) // 2

for a in alist:
    num = cdict[a]
    if num in resdict:
        # print('used')
        print(resdict[num])
        continue
    # print('not used')
    if a in cdict:
        cdict[a] -= 1
        temp = 0
        for k,v in cdict.items():
            temp += v*(v-1)//2
        print(temp)
        resdict[num] = temp
        cdict[a] += 1
    else:
        print(maxi)
### BUGGY CODE ###

n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        part = s[i:j]
        if part in s[j:]:
            _max = max(_max, j-i)
        else:
            break
print(_max)

### FIXED CODE ###

n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        if _max >= j-i:
            continue
        part = s[i:j]
        if part in s[j:]:
            _max = j-i
        else:
            break
print(_max)
### BUGGY CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
N=int(input())
P=list(map(int,input().split()))
for i in range(N):
    P[i]-=1
A=[30000*i for i in range(1,N+1)]
B=list(reversed(A))


lst=set(P[1:])
for i in range(1,N):
    for m in range(N):
        A[m]+=1
        if not m in lst:
            B[m]-=1
    lst.remove(P[i])

print(" ".join([str(i) for i in A]))
print(" ".join([str(i) for i in B]))


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
N=int(input())
P=list(map(int,input().split()))
for i in range(N):
    P[i]-=1
A=[30000*i for i in range(1,N+1)]
B=list(reversed(A))
ruiA=[]
ruiB=[]


#lst=set(P[1:])
count=1
for i in range(0,N)[::-1]:
    B[P[i]]-=count
    """for m in lst:
        B[m]-=1
    lst.add(P[i])"""
    count+=1

print(" ".join([str(i) for i in A]))
print(" ".join([str(i) for i in B]))
### BUGGY CODE ###

#D
S = list(str(input()))
N = len(S)

U = []
for i in range(N):
    U.append(int(S[N-i-1]))


DP = [-1]*(N+1)
DP[0] = 0
now = 0
for i,u in enumerate(U):
    now+=int(u)*(10**i)
    now%=2019
    DP[i+1] = now
    
#print(DP)
tyo = [0]*2019
for dp in DP:
    tyo[dp]+=1

ans = 0
for t in tyo:
    ans+=(t*(t-1))//2
    
print(ans)




### FIXED CODE ###

#D
S = list(str(input()))
N = len(S)

U = []
for i in range(N):
    U.append(int(S[N-i-1]))


DP = [-1]*(N+1)
DP[0] = 0
now = 0
pnow = 1
for i,u in enumerate(U):
    pnow*=10
    pnow%=2019
    now+=int(u)*pnow
    now%=2019
    DP[i+1] = now
    
#print(DP)
tyo = [0]*2019
for dp in DP:
    tyo[dp]+=1

ans = 0
for t in tyo:
    ans+=(t*(t-1))//2
    
print(ans)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    balls = {}

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1

    while len(set(A)) > k:
        
        minValue = 200000
        maxValue = 0

        for key, value in balls.items():
            if value < minValue and value > 0:
                minValue = value
                minKey = key
        
        for key, value in balls.items():
            if value > maxValue:
                maxValue = value
                maxKey = key
        
        A[A.index(minKey)] = maxKey
        balls[minKey] -= 1
        balls[maxKey] += 1

        res += 1
    
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    res = 0
    balls = {}
    bucket = [[] for _ in range(n+1)]

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    for key, value in balls.items():
        bucket[value].append(key)

    for i in range(len(bucket)):
        for j in range(len(bucket[i])):
            if bucket[i] != [] and len(balls) > k:
                res += i
                balls.pop(bucket[i][j])

    print(res)

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

nums = [int(e) for e in input().split()]
Min=nums[0]
y=nums[1]
t=True
while t:
    a = abs(Min - y)
    if(a<Min):
        Min = a
    elif(a>Min):
        t = False
print(Min)

### FIXED CODE ###

nums = [int(e) for e in input().split()]
Min=nums[0]
y=nums[1]
ans = Min % y
t = True
if (ans <= Min):
    Min = ans
    while t:
        a = abs(Min - y)
        if(a<Min):
            Min = a
        elif(a>Min):
            break
    print(Min)
else:
    print(ans)
### BUGGY CODE ###

"""
AtCoder :: Beginner Contest 174 :: Logs
https://atcoder.jp/contests/abc174/tasks/abc174_e
"""
import sys
import math
import heapq

class Log:
    def __init__(self, length):
        self.init_length = length
        self.curr_length = length
        self.cuts = 0

    def cut(self):
        self.cuts += 1
        self.curr_length = self.init_length / (self.cuts + 1)

    def __lt__(self, other):
        """Reversed, for heapq"""
        if self.curr_length == other.curr_length:
            return self.cuts > other.cuts
        else:
            return self.curr_length > other.curr_length


def main():
    """Main program."""
    log_count, cut_count = (int(i) for i in sys.stdin.readline().split())
    logs = [Log(float(i)) for i in sys.stdin.readline().split()]
    heapq.heapify(logs)
    for _ in range(cut_count):
        log = heapq.heappop(logs)
        log.cut()
        heapq.heappush(logs, log)
    print(math.ceil(logs[0].curr_length))


if __name__ == '__main__':
    main()


### FIXED CODE ###

"""
AtCoder :: Beginner Contest 174 :: Logs
https://atcoder.jp/contests/abc174/tasks/abc174_e
"""
import sys
from math import ceil


def main():
    """Main program."""
    log_count, cut_count = (int(i) for i in sys.stdin.readline().split())
    logs = [int(i) for i in sys.stdin.readline().split()]
    high = max(logs)
    low = 1
    soln = high
    # Binary search for the answer.
    while low <= high:
        mid = (low + high) // 2
        cuts_needed = sum([int(ceil(log / mid)) - 1 for log in logs])
        if cuts_needed <= cut_count:
            soln = min(soln, mid)
            high = mid - 1
        else:
            low = mid + 1
    print(soln)


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

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=1000000000000000000

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
    if multi_sum > LIMIT:
        multi_sum=-1
else:
    multi_sum=0

print(multi_sum)



### FIXED CODE ###

n=int(input())
a_list=list(map(int, input().split()))
multi_sum=1
LIMIT=1000000000000000000

if 0 not in a_list:
    for a_i in a_list:
        multi_sum*=a_i
        if multi_sum > LIMIT:
            multi_sum=-1
            break
else:
    multi_sum=0

print(multi_sum)
### BUGGY CODE ###

import sys

n=int(input())
alst=list(map(int,sys.stdin.readline().strip().split()))

cumsum=[[0]*(n+1) for i in range(60)]

md=10**9+7

for i in range(1,n+1):
    a=alst[i-1]
    dig=0
    while dig<60:
        bit=a%2
        cumsum[dig][i]=cumsum[dig][i-1]+bit
        dig+=1
        a//=2

ans=0
ceff=1

for d in range(60):
    ret=0
    for i in range(1,n):
        ret+=(cumsum[d][i]-cumsum[d][i-1])*(n-i-cumsum[d][n]+cumsum[d][i])
        ret+=(1-cumsum[d][i]+cumsum[d][i-1])*(cumsum[d][n]-cumsum[d][i])
    ans=(ans+ceff*ret)%md
    ceff=(2*ceff)%md

print(ans)



### FIXED CODE ###

import sys

n=int(input())
alst=list(map(int,sys.stdin.readline().strip().split()))

cumsum=[[0]*(n+1) for i in range(60)]

md=10**9+7

for i in range(1,n+1):
    a=alst[i-1]
    dig=0
    while dig<60:
        bit=a%2
        cumsum[dig][i]=cumsum[dig][i-1]+bit
        dig+=1
        a//=2

ans=0
ceff=1

for d in range(60):
    ret=0
    for i in range(1,n):
        ret+=(cumsum[d][i]-cumsum[d][i-1])*(n-i-cumsum[d][n]+cumsum[d][i])
        ret+=(1-cumsum[d][i]+cumsum[d][i-1])*(cumsum[d][n]-cumsum[d][i])
    ans=(ans+ceff*ret)%md
    ceff=(2*ceff)%md

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

s = input()
q = int(input())

# 毎回反転させていたら時間切れになる
is_reverse = False
for _ in range(q):
    query = input().split()
    if len(query) == 1:
        if is_reverse:
            is_reverse = False
        else:
            is_reverse = True
    else:
        _, f, c = query
        if f == '1':
            if is_reverse:
                s = s + c
            else:
                s = c + s
        else:
            if is_reverse:
                s = c + s
            else:
                s = s + c

if is_reverse:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###

s = input()
q = int(input())

# 毎回反転させていたら時間切れになる
is_reverse = False
forward = dict()  # あとで別のデータ構造に変更する
backward = dict()  # あとで別のデータ構造に変更する
# forward = list()
# backward = list()
forward_num = 0
backward_num = 0

for _ in range(q):
    query = input().split()
    if len(query) == 1:
        if is_reverse:
            is_reverse = False
        else:
            is_reverse = True
    else:
        _, f, c = query
        if f == '1':
            if is_reverse:
                backward[backward_num] = c
                backward_num += 1
                # s = s + c
                # backward.append(c)
            else:
                forward[forward_num] = c
                forward_num += 1
                # s = c + s
                # forward.insert(0, c)
        else:
            if is_reverse:
                forward[forward_num] = c
                forward_num += 1
                # forward.insert(0, c)
                # s = c + s
            else:
                backward[backward_num] = c
                backward_num += 1
                # backward.append(c)
                # s = s + c

# print(forward)
# print(backward)
forward = list(forward.values())[::-1]
backward = list(backward.values())
# print(is_reverse)
# print(forward)
# print(backward)

if is_reverse:
    s = s[::-1]
    print(''.join(backward)[::-1] + s + ''.join(forward)[::-1])
else:
    print(''.join(forward) + s + ''.join(backward))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

tree = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)

adds = defaultdict(int)
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x

def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    for v in tree[i]: dig(v,tmp)

ans = defaultdict(int)
tmp = 0
dig(1,tmp)

for i in range(1,N+1):
    print(ans[i], end=' ')
print()

### FIXED CODE ###

from queue import deque
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = {i+1:0 for i in range(N)}
for i in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

checked = [False for i in range(N+1)]
myq = deque()
myq.append(1)

while myq:
    v = myq.pop()
    checked[v] = True
    for n in tree[v]:
        if not checked[n]:
            ans[n] += ans[v]
            myq.append(n)
print(' '.join(str(ans[i]) for i in range(1,N+1)))
### BUGGY CODE ###

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

for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
a = collections.Counter(A)


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

from itertools import permutations

input()

ans = 0
for tup in permutations(map(int, input().split())):
    tmp = tup[0]
    for t in tup[1:]:
        tmp = (tmp + t) / 2
    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

input()
V = sorted(map(int, input().split()))

ans = V[0]
for v in V[1:]:
    ans = (ans + v) / 2

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

N = int(input())
S = input()
def isok(n):
    for i in range(N-2*n+1):
        now = S[i:i+n]
        for j in range(i+n, N-n+1):
            if now == S[j:j+n]:
                return True
    return False

left = 0
right = N//2+1

while right - left > 1:
    mid = left + (right-left)//2
    if not isok(mid):
        right = mid
    else:
        left = mid




print(left)


### FIXED CODE ###

N = int(input())
S = input()


r = 1
ans = 0
for l in range(N):

    while True:
        #print(S.rfind(S[l:r+1]), S[l:r+1], l, r)

        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

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

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

b.sort(reverse=True)
ans = 0

while k > 0:
    if n == 0:
        break
    else:
        b.pop(0)
        k -= 1
        n -= 1

if n == 0:
    print('0')
else:
    print(sum(b))

### FIXED CODE ###

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

b.sort(reverse=True)
ans = 0

del b[:k]
n -= k

if n < 0:
    print('0')
else:
    print(sum(b))
### BUGGY CODE ###

import sys 

def func():
    n=int(input())
    print(0)
    sys.stdout.flush()
    gl=input()
    if gl == 'Vacant': 
        return
    print(n-1)
    sys.stdout.flush()
    gr=input()
    if gr == 'Vacant':
        return
    l=0
    r=n-1
    m=0
    while l<r-1:
        m=(l+r)>>1
        print(m)
        sys.stdout.flush()
        gm=input()
        if gm == 'Vacant' : 
            return  
        if (m-l)%2==0 and gm==gl :
            l=m
        elif (m-l)%2==1 and gm!=gl : 
            l=m
        else :
            r=m

    if m==l : 
        print(r)
        sys.stdout.flush()
    else: 
        print(l)
        sys.stdout.flush()
    return 

func()


### FIXED CODE ###

import sys 

def func():
    n=int(input())
    print(0)
    sys.stdout.flush()
    gl=input()
    if gl == 'Vacant': 
        return
    print(n-1)
    sys.stdout.flush()
    gr=input()
    if gr == 'Vacant':
        return
    l=0
    r=n-1
    m=0
    while l<r-1:
        m=(l+r)>>1
        print(m)
        sys.stdout.flush()
        gm=input()
        if gm == 'Vacant' : 
            return  
        if (m-l)%2==0 and gm==gl :
            l=m
        elif (m-l)%2==1 and gm!=gl : 
            gl=gm
            l=m
        else :
            gr=gm
            r=m

    if m==l : 
        print(r)
        sys.stdout.flush()
    else: 
        print(l)
        sys.stdout.flush()
    return 

func()