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

import sys
input=sys.stdin.readline
N = int(input())
#S = input()[:-1]
#N,M = map(int,input().split())
#S,T = map(str,input().split())
A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
def binary_search(S,key): 
    left  = 0
    right = N
    while left < right:
        mid = (left+right) // 2
        if S[mid] == key:
            return mid
        elif S[mid] > key:
            right = mid
        else:
            left = mid + 1
    return mid
d = 0
A.sort()
for i in range(N-1):
    for j in range(i+1,N):
        s = A[i]+A[j]
        dex = binary_search(A,s)
        while A[dex] >= s :
            dex -= 1
        d = d + dex - j
print(d)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from bisect import bisect_left
N = int(input())
#S = input()[:-1]
#N,M = map(int,input().split())
#S,T = map(str,input().split())
A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
d = 0
A.sort()
for i in range(N-2):
    for j in range(i+1,N-1):
        s = A[i]+A[j]
        dex = bisect_left(A,s)
        if dex > j:
          d += dex -j -1
print(d)
### BUGGY CODE ###

from collections import*
from heapq import*
n,m,*a=map(int,open(0).read().split())
t=[-1]*n
def r(x):
  while~t[x]:x=t[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x!=y:
    if t[x]>t[y]:x,y=y,x
    t[x]+=t[y]
    t[y]=x
d=defaultdict(list)
for x,y in zip(*[iter(a[n:])]*2):u(x,y)
for i,v in enumerate(a[:n]):d[r(i)]+=v,
if len(d)<2:
  print(0)
  exit()
*d,=map(sorted,d.values())
c=sum(heappop(t)for t in d)
l=[]
for t in d:l+=t
i=len(d)-2
print(i>len(l)and'Impossible'or c+sum(sorted(l)[:i]))

### FIXED CODE ###

from collections import*
from heapq import*
def main():
  n,m,*a=map(int,open(0).read().split())
  table=[-1]*n
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    s1=root(x)
    s2=root(y)
    if s1!=s2:
      if table[s1]>table[s2]:s1,s2=s2,s1
      table[s1]+=table[s2]
      table[s2]=s1
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):unite(x,y)
  for i,v in enumerate(a[:n]):d[root(i)]+=v,
  if len(d)<2:
    print(0)
    return
  *d,=map(sorted,d.values())
  c=sum(heappop(t)for t in d)
  l=[]
  for t in d:l+=t
  i=len(d)-2
  if len(l)<i:
    print('Impossible')
  else:
    print(c+sum(sorted(l)[:i]))
main()
### BUGGY CODE ###

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

#list_aaa = []
#
#for i in range(M):
#    L,R = map(int,input().split())
#    aaa = set(range(L,R+1))
#    list_aaa.append(aaa)
#print(list_aaa)

#and_set = list_aaa[0]

for i in range(M):
    L,R = map(int,input().split())
    aaa = set(range(L,R+1))
    if i == 0:
        and_set = aaa
    else:
        and_set = and_set.intersection(aaa)


print(len(and_set))



### FIXED CODE ###

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

L_list = []
R_list = []

for i in range(M):
    L,R = map(int,input().split())
    L_list.append(L)
    R_list.append(R)
L_max = max(L_list)
R_min = min(R_list)

#print(range(L_max,R_min+1))
print(len(range(L_max,R_min+1)))
### BUGGY CODE ###

INF = float('inf')

class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

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

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, True, i, X))
    events.append((T - X, False, i, X))
events.sort()

tree = MinSegTree(N)

D = [int(input()) for _ in range(Q)]
M = len(events)
now = 0
ans = []
for d in D:
    while now < M and events[now][0] <= d:
        _, isStart, i, x = events[now]
        if isStart:
            tree.update(i, x)
        else:
            tree.update(i, INF)
        now += 1
    ans.append(tree.query(0, N))

for a in ans:
    print(-1 if a == INF else a)


### FIXED CODE ###

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

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, 0, X))
    events.append((T - X, 1, X))

for _ in range(Q):
    events.append((int(input()), 2, 0))

events.sort()

cnt = defaultdict(int)
cnt[INF] += 1
que = [INF]

for t, flag, x in events:
    if flag == 0:
        if cnt[x] == 0:
            heappush(que, x)
        cnt[x] += 1
    elif flag == 1:
        cnt[x] -= 1
    else:
        while cnt[que[0]] == 0:
            heappop(que)
        print(que[0] if que[0] != INF else -1)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



def main():
    N, M = map(int, input().split())
    unf = UnionFind(N)
    for i in range(M):
        A, B = map(int, input().split())
        if not unf.same(A-1, B-1):
            unf.union(A-1, B-1)
    
    groups = unf.all_group_members()

    sizes = []
    for k, i in groups.items():
        sizes.append(len(groups[k]))
    
    group_nums = len(sizes)
    print(max(sizes))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



def main():
    N, M = map(int, input().split())
    unf = UnionFind(N)
    for i in range(M):
        A, B = map(int, input().split())
        if not unf.same(A-1, B-1):
            unf.union(A-1, B-1)

    print(-min(unf.parents))

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

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

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)


# print('weight')
# print(weight)
# print('value')
# print(value)


def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# print(dp)
# print(weight)
# print(value)
# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        # if j+weight[i] <= W:
        #     dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])




### FIXED CODE ###

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

weight = []
value = []

for i in range(N):
    w, v = list(map(int, input().split()))
    weight.append(w)
    value.append(v)

def dfs(index, v, w):
    x = 0
    if (index >= N):
        return v
    if (w + weight[index] <= W):
        x = dfs(index+1, v+value[index], w+weight[index])
    y = dfs(index+1,v,w)

    return max(x, y)


# ans = dfs(0, 0, 0)

dp = []

for i in range(N+1):
    dp.append([])
    for j in range(W+1):
        dp[i].append(0)
    
# max value = dp[何個まで見たか][現在の重さ]
for i in range(N):
    for j in range(W+1):
        # if j+weight[i] <= W:
        #     dp[i+1][j+weight[i]] = max(dp[i][j+weight[i]], dp[i][j]+value[i])
        # else:
        #     dp[i+1][j] = dp[i][j]
        # if 
        if j >= weight[i]:
            dp[i+1][j] = max(dp[i][j-weight[i]]+value[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]


print(dp[N][W])
### BUGGY CODE ###

n = list(map(int, (input()).split(' ')))
#print(n)
x = [ i   for i in range(n[0]+1)]
#y = [ i   for i in range(n[1]+1)]
#z = [ i   for i in range(n[1]+1)]
#print(x)
counter = 0
for x1 in x:
  for y1 in x:
    for z1 in x:
      if x1+y1+z1== n[1]:
        counter +=1

        
print(counter)        

### FIXED CODE ###

n = list(map(int, (input()).split(' ')))
#n = [2500,7500]
#print(n)
x = [ i   for i in range(n[0]+1)]
#y = [ i   for i in range(n[1]+1)]
#z = [ i   for i in range(n[1]+1)]
#print(x)
counter = 0
if n[0]*3 >= n[1]:
  for x1 in x:
    for y1 in x:
      if 0<= n[1]-x1-y1 <=n[0]  :
          counter +=1

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

n = int(input())

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

final = 1

for i in a:
    final *= i
    
if final > 1000000000000000000:
    print(-1)
else:
    print(final)

### FIXED CODE ###

n = int(input())

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

final = 1

if 0 in a:
    print(0)
    
else:
    for i in a:
        final *= i
        if final > 1000000000000000000:
            break
    if final > 1000000000000000000:
        print(-1)
    else:
        print(final)
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort()
f = 0


def C(n, k, mod):
    x,y = 1,1
    while k > 0:
        x *= n ; y *= k
        n, k = n-1, k-1
        x %= mod ; y %= mod
    return x * pow(y, mod-2, mod)


if k >= 2:

    for i in range(n-k+1):
        for j in range(i+k-1,n):
            f += ((a[j]-a[i]) * C(j-i-1,k-2,mod)) % mod

else: f = 0
print(f % mod)


### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
p = mod
a.sort(reverse = True)
# print(a)
ans = 0

#
# def C(n, k):
#     if k == 0:
#         return 1
#     elif n < k or k < 0:
#         return 0
#     else:
#         x,y = 1,1
#         while k > 0:
#             x *= n
#             y *= k
#             n, k = n-1, k-1
#
#         return x * pow(y, mod-2, mod) % mod
#

fac = [0] * (n + 1)
fac[0] = 1
for i in range(n):
    fac[i + 1] = fac[i] * (i + 1) % mod


def C(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1)
    ans %= mod



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

s=input()
n=len(s)
a=[]
c=[0]*n
for i in range(n-1):
	if s[i]!=s[i+1]:
		a.append(i)
for i in range(n):
	if s[i]=="L":
		for j in range(n):
			if s[i-j]=="R":
				idou=j
				break
		if idou%2==0:
			c[i-j]+=1
		else:
			c[i-j+1]+=1
	else:
		for j in range(n):
			if s[i+j]=="L":
				idou=j
				break
		if idou%2==0:
			c[i+j]+=1
		else:
			c[i+j-1]+=1
print(*c)



### FIXED CODE ###

import bisect
s=input()
n=len(s)
a=[]
c=[0]*n
for i in range(n-1):
	if s[i]!=s[i+1]:
		a.append(i)


for i in range(n):
	if s[i]=="L":
		pp=bisect.bisect_left(a,i)
		idou=i-a[pp-1]+1
		if idou%2==0:
			c[a[pp-1]+1]+=1
		else:
			c[a[pp-1]]+=1
	else:
		pp=bisect.bisect_left(a,i)
		idou=a[pp]-i
		if idou%2==0:
			c[a[pp]]+=1
			
		else:
			c[a[pp]+1]+=1
			
print(*c)
### BUGGY CODE ###

def gcd(x,y):
    if y==0:
        return x
    return gcd(y,x%y)

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
# lcm %= MOD
ans = 0
for i in A:
    ans += lcm*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)


### FIXED CODE ###

def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)

def func(x):
    if x <= 1:
        return []
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            count = 0
            while x%i==0:
                x //= i
                count += 1
            return [[i,count]]+func(x)
    return [[x,1]]
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = [0]*(10**6)
for i in A:
    for a,b in func(i):
        lcm[a] = max(lcm[a],b)
L = 1
for i in range(2,10**6):
    L *= pow(i,lcm[i],MOD)
    L %= MOD
ans = 0
for i in A:
    ans += L*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
import math
import copy
from functools import lru_cache
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    local_robots = copy.deepcopy(robots)
    for i, current in enumerate(robots):
        if count_collisions(current, local_robots) > 0:
            local_robots.remove(current)
            total -= 1
        else:
            break
            
    return total

def count_collisions(current, robots):
    count = 0
    for robot in robots:
        if collision(current[0], current[1], robot[0], robot[1]):
            count += 1
    return count

@lru_cache(maxsize=None)
def collision(currentX, currentL, robotX, rootL):
    return robotX < currentX and robotX+ rootL > currentX - currentL or currentX < robotX and currentX + currentL > robotX - rootL

N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = list(reversed(sorted(ROBOTS, key=lambda x: count_collisions(x, ROBOTS))))
print(solve(ROBOTS))

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000000)
 
def solve(robots):
    total = len(robots)
    prev = None
    for current in robots:
        if prev and prev[0] + prev[1] > current[0] - current[1]:
            total -= 1
        else:
            prev = current
            
    return total
 
N, = map(int, input().split())
ROBOTS = [list(map(int, input().split())) for _ in range(N)]
ROBOTS = sorted(ROBOTS, key=lambda x: x[0] + x[1])
print(solve(ROBOTS))
### BUGGY CODE ###

import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
maxA = np.max(A)
    
dp = np.full(H+1, np.inf)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        if i < A[j]:
            dp[i] = min(dp[i], B[j])
        else:
            dp[i] = min(dp[i], dp[i-A[j]] + B[j])
            
print(int(dp[H]))

### FIXED CODE ###

import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
dp = np.full(H+1, np.inf)

dp[0] = 0
for i in range(1,H+1):
    dp[i] = np.amin( dp[np.maximum(i-A,0)] + B )

print(int(dp[H]))
### BUGGY CODE ###


n = int(input())
x_str = input().split()
x = [int(c) for c in x_str]

x_len = len(x)
center = (x_len - 1)//2

c_x = x[:]
c_x.sort()

for i in range(x_len):
    cc_x = c_x[:]
    cc_x.remove(x[i])
    print(cc_x[center])


### FIXED CODE ###


import numpy as np

n = int(input())
x_str = input().split()
xs = np.array([int(c) for c in x_str])

xs_len = len(xs)
center = (xs_len - 1)//2

c_xs = np.sort(xs)

for x in xs:
    if x <= c_xs[center]:
        print(c_xs[center+1])
    else:
        print(c_xs[center])
### BUGGY CODE ###

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

day_to_cost = {}
for a, b in AB:
    if day_to_cost.get(a) is None:
        day_to_cost[a] = [b]
    else:
        day_to_cost[a].append(b)

ans = 0
candidate = []
for i in range(1, M+1):
    candidate += day_to_cost.get(i, [])
    if candidate:
        work_cost = max(candidate)
        candidate.remove(work_cost)
        ans += work_cost


print(ans)


### FIXED CODE ###

import heapq as pq

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

day_to_reward = {}
for a, b in AB:
    if day_to_reward.get(a) is None:
        day_to_reward[a] = [b]
    else:
        day_to_reward[a].append(b)

ans = 0
candidate = []
for i in range(1, M+1):
    for reward in day_to_reward.get(i, []):
        pq.heappush(candidate, - reward)
    if candidate:
        work_reward = - pq.heappop(candidate)
        ans += work_reward


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

Q = int(input())
mod = int(1e+6 + 3)

def doubling(n, m):
  y = 1
  p = n
  while m != 0:
    if m % 2 == 1:
      y *= p
      y %= mod
    m //= 2
    p *= p
    p %= mod
  return y

def inved(s):
  x, y, u, v, k, l = 1, 0, 0, 1, s, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

frac = [1]
for i in range(mod):
  frac.append((frac[i]*(i+1))%mod)

for i in range(Q):
  x, d, n = map(int, input().split())
  if x == 0:
    print(0)
  else:
    if d == 0:
      print(doubling(x, n))
    else:
      if n >= mod:
        print(0)
      else:
        xinvd = x * inved(d) - 1
        xinvd %= mod
        if xinvd + n >= mod:
          print(0)
        else:
          dn = doubling(d, n)
          print((dn * frac[xinvd + n] * inved(frac[xinvd])) % mod)

### FIXED CODE ###

Q = int(input())
mod = int(1e+6 + 3)

def doubling(n, m):
  y = 1
  p = n
  while m != 0:
    if m % 2 == 1:
      y *= p
      y %= mod
    m //= 2
    p *= p
    p %= mod
  return y

def inved(s):
  x, y, u, v, k, l = 1, 0, 0, 1, s, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

frac = [1 for _ in range(mod+1)]
invf = [1 for _ in range(mod+1)]
invf[mod] = 0
for i in range(mod):
  frac[i+1] = (frac[i] * (i+1)) % mod
invf[mod-1] = inved(frac[mod-1])
for i in range(mod-1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod

for i in range(Q):
  x, d, n = map(int, input().split())
  if x == 0:
    print(0)
  else:
    if d == 0:
      print(doubling(x, n))
    else:
      if n >= mod:
        print(0)
      else:
        xinvd = x * inved(d) - 1
        xinvd %= mod
        if xinvd + n >= mod:
          print(0)
        else:
          dn = doubling(d, n)
          print((dn * frac[xinvd + n] * invf[xinvd]) % mod)
### BUGGY CODE ###

s=input()
n=len(s)
a=[0]*2019
a[0]=1
k=0
ans=0
for i in range(n):
  k=(k+int(s[n-1-i])*10**i)%2019
  a[k]+=1
for i in range(2019):
  ans+=a[i]*(a[i]-1)*0.5

print(int(ans))

### FIXED CODE ###

s=input()
n=len(s)
a=[0]*2019
a[0]=1
k=0
ans=0
mod=1
for i in range(n-1,-1,-1):
  k=(k+int(s[i])*mod)%2019
  mod=(mod*10)%2019
  a[k]+=1
for i in a:
  ans+=i*(i-1)*0.5

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

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

INF = 10**12
cost = [[INF] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < INF else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

#二分探索
N = int(input())
S = input()
l = 0
r = N

ans = 0
while r - l > 1:
    mid = (l + r) // 2
    for i in range(N - (2*mid) + 1 ):
        if S[i:i+mid] in S[i+mid:]:
            l = mid
            ans = mid
            break
    else:
        r = mid
        
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
B = 127
MOD = 10 ** 11 + 7

H = [0] * (len(S) + 1)
P = [1] * (len(S) + 1)
b = pow(B, N-1)
for i in range(len(S)):
    H[i+1] = (H[i] + ord(S[i]) * b) % MOD
    P[i+1] = (P[i] * B) % MOD
    b //= B

l = 0
r = N
ans = 0
while r - l > 1:
    mid = (l + r) // 2
    tmp = {}
    for i in range(N - mid + 1):
        h = ((H[mid+i] - H[i]) * P[mid+i-1]) % MOD
        if h in tmp and i - tmp[h] >= mid:
            l = mid
            ans = mid
            break
        else:
            if not h in tmp:
                tmp[h] = i
    else:
        r = mid
        
print(ans)