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

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

#N = int(input())
#S = str(input())
#N = 13
#S = "strangeorange"
 
lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = [""]*(N - 2*mid + 1)
    for i in range(N - 2*mid + 1):
        s[i] = S[i:mid+i]
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

### FIXED CODE ###

N = int(input())
S = str(input())
#N = 13
#S = "strangeorange"

lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = set()
    for i in range(N - 2*mid + 1):
        s.add(S[i:mid+i])
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)
### BUGGY CODE ###

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

cnt = 0
for i in range(1000):
  c = [str(i // 100), str((i // 10) % 10), str(i % 10)]
  f = 0
  for j in range(N):
    if S[j] == c[f]:
      f += 1
    if f == 3:
      break
  if f == 3:
    cnt += 1
print(cnt)


### FIXED CODE ###

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

cnt = 0
for i in range(1000):
  c = str(i).zfill(3)
  if c[0] in S:
        index1 = S.index(c[0])
        if c[1] in S[index1+1:]:
            index2 = index1 + 1 + S[index1+1:].index(c[1])
            if c[2] in S[index2+1:]:
                cnt+=1
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())
cnt = set(range(1,n+1))
for i in range(m):
    l,r = map(int,input().split())
    cnt = cnt&set(i for i in range(l,r+1))
print(len(cnt))

### FIXED CODE ###

n,m = map(int,input().split())
a,b = 1,n
for i in range(m):
    l,r = map(int,input().split())
    a,b = max(a,l),min(b,r)
print(max(b-a+1,0))
### BUGGY CODE ###

from collections import deque

n = int(input())
a = list(map(int,input().split()))
m = 1000
ans = 1000
ans_list=[]

q = deque([[1000, 0, n, 0]])

while len(q) != 0:
    tmp = q.popleft()
    m,k,d,i = tmp[0],tmp[1],tmp[2],tmp[3]
    if d == 0 and m > ans:
        ans = m
        ans_list.append(m)
    elif d > 1:
        x = m//a[i]
        q.append([m-(x*a[i]),x+k,d-1,i+1])
        q.append([m+(k*a[i]),0,d-1,i+1])
        q.append([m,k,d-1,i+1])
    elif d == 1:
        q.append([m+(k*a[i]),0,d-1,i+1])

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
k = 0
ans = 1000

for i in range(n-1):
    if a[i] < a[i+1]:
        k = ans//a[i]
        ans -= a[i]*k
        ans += a[i+1]*k

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

N = int(input())
ans = []
for n in range(1,N+1):
    result = 0
    for x in range(1,int(n**(1/2))+1):
        if x**2 < n:
            for y in range(1,int(n**(1/2))+1):
                if (x+y)**2-4*((x**2+y**2+x*y) - n) >= 0:
                    z = (-(x+y)+((x+y)**2-4*((x**2+y**2+x*y) - n))**(1/2))/2
                    if (z%1)==0 and z > 0:
                        result += 1
                            
    ans += [result]

print("\n".join(map(str,ans)))

### FIXED CODE ###

import itertools
N = int(input())
ans = [0 for i in range(0,N)]
for x, y, z in itertools.product(range(1,int(N**(1/2)+1)),range(1,int(N**(1/2)+1)),range(1,int(N**(1/2)+1))):
    kai = x**2+y**2+z**2+x*y+x*z+y*z
    if 0 < kai <= N:
        ans[kai-1] += 1

print("\n".join(map(str,ans)))
### BUGGY CODE ###


def E(x):
    ans = 0
    for i in range(x):
        ans += (i+1)
    ans /= x
    return ans

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

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

res = []

for i in range(len(p)-k+1):
    temp = 0
    for j in range(k):
        temp +=E(p[i+j])
    res.append(temp)
print(max(res))


### FIXED CODE ###

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

p = list(map(int,input().split()))
counter_li = []
first = 0
for i in range(k):
    first+=p[i]
counter_li.append(first)
for i in range(1,len(p)-k+1):
    counter_li.append(counter_li[i-1]+ p[i+k-1] - p[i-1])
print(max(counter_li)/2+k/2)
### BUGGY CODE ###

from collections import deque
from bisect import bisect_left

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

last = deque()
pre = -C - 1
for i, s in enumerate(reversed(S)):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break
lastset = set(last)

count = 0
pre = -C - 1
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    if i in lastset and count <= bisect_left(last, i) + 1:
      print(i + 1)
    pre = i
    count += 1
    if count == K:
      break

### FIXED CODE ###

from collections import deque

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

last = deque()
pre = -C - 1
for i, s in enumerate(reversed(S)):
  if i > pre + C and s == 'o':
    last.appendleft(N - 1 - i)
    pre = i
    if len(last) == K:
      break

count = 0
pre = -C - 1
x = last.popleft()
for i, s in enumerate(S):
  if i > pre + C and s == 'o':
    count += 1
    while x < i:
      x = last.popleft()
    if x == i and count + len(last) == K:
      print(i + 1)
    pre = i
    if count == K:
      break
### BUGGY CODE ###

n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
for i in range(n):
    flag = min(a[:i+1])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))

### FIXED CODE ###

n,t = map(int,input().split())
a = list(map(int,input().split()))
ans = [0]*n
flag = float("inf")
for i in range(n):
    flag = min(flag,a[i])
    ans[i] = a[i]-flag
print(ans.count(max(ans)))
### BUGGY CODE ###

import heapq
import itertools
N,M,R=map(int, raw_input().split())
r=map(int, raw_input().split())

cost=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]
nl=[ [] for i in range(N+1) ]

for i in range(M):
	A,B,C=map(int, raw_input().split())
	cost[A][B]=C
	cost[B][A]=C
	nl[A].append(B)
	nl[B].append(A)


for i in range(N+1): cost[i][i]=0


def Dij(start):

	#Initialize
	d=[float("inf") for i in range(N+1)]
	d[start]=0
	q=[]
	heapq.heappush(q,(0,start))
	
	while len(q)!=0:
		tmp=heapq.heappop(q)
		u=tmp[1]

		for v in nl[u]:
			alt=d[u]+cost[u][v]
			if d[v]>alt:
				d[v]=alt
				heapq.heappush(q,(alt,v))
	return d


l=list(itertools.permutations(r))

C=[[]]
for i in range(1,N+1):
	C.append(Dij(i))

ans=float("inf")


for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		dist+=C[prev][cur]
		prev=cur
	ans=min(ans,dist)

print ans




### FIXED CODE ###

import heapq
import itertools
N,M,R=map(int, raw_input().split())
r=map(int, raw_input().split())

cost=[ [ float("inf") for i in range(N+1)] for i in range(N+1) ]
nl=[ [] for i in range(N+1) ]

for i in range(M):
	A,B,C=map(int, raw_input().split())
	cost[A][B]=C
	cost[B][A]=C
	nl[A].append(B)
	nl[B].append(A)


for i in range(N+1): cost[i][i]=0


def Dij(start):

	#Initialize
	d=[float("inf") for i in range(N+1)]
	d[start]=0
	q=[]
	heapq.heappush(q,(0,start))
	
	while len(q)!=0:
		tmp=heapq.heappop(q)
		u=tmp[1]

		for v in nl[u]:
			alt=d[u]+cost[u][v]
			if d[v]>alt:
				d[v]=alt
				heapq.heappush(q,(alt,v))
	return d


l=list(itertools.permutations(r))

C={}
for i in r:
	C[i]=Dij(i)


ans=float("inf")


for i in l:
	dist=0
	for j in range(R):
		if j==0:
			prev=i[j]
			continue
		cur=i[j]
		dist+=C[prev][cur]
		prev=cur
	ans=min(ans,dist)

print ans
### BUGGY CODE ###

s = input()
mod = 2019
a = [[int(s[0]),1]]
count = 0
for i in s[1:]:
    b = []
    c = 0
    for j in a:
        d = (j[0]*10+int(i))%2019
        if d == int(i):
            c = 1
            b.append([d,j[1]+1])
            if d == 0:
                count += j[1]+1
        else:
            b.append([d,j[1]])
            if d == 0:
                count += j[1]
    if c == 0:
        b.append([int(i),1])
    a = b
    
print(count)

### FIXED CODE ###

from collections import Counter
s = input()
a = [0]
mod = 2019
for i,j in enumerate(s[::-1]):
    a.append(a[-1]+int(j)*pow(10,i,mod))
    a[-1] %= mod
b = Counter(a)
ans = 0
for i in b.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
import sys

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

N, M = map(int, input().split())
A = []
B = []
neighbor = [[0 for x in range(N)] for y in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    neighbor[a][b] = 1
    neighbor[b][a] = 1

neighbor = csr_matrix(neighbor)

ans = []
d, p = shortest_path(neighbor, return_predecessors=True, indices=0)

for i in range(1,N):
    if p[i]<0:
        print("No")
        sys.exit(0)
    else:
        ans.append(p[i]+1)
print("Yes")
for i in range(N-1):
    print(ans[i])


### FIXED CODE ###

from collections import deque

N,M = map(int, input().split())
ways = [[] for _ in range(N+1)]

for i in range(M):
    a,b = map(lambda x: int(x), input().split())
    ways[a].append(b)
    ways[b].append(a)

dq = deque([1])
sign = [None] * (N+1)
sign[0] = 0
sign[1] = 0

while(dq):
    now = dq.popleft()
    for w in ways[now]:
        if not sign[w]:
            sign[w] = now
            dq.append(w)

if None in sign:
    print("No")
else:
    print("Yes")
    for i in range(2, N+1):
        print(sign[i])
### BUGGY CODE ###

N = int(input())
S = input().rstrip()

dp = [[[[False for _ in range(11)] for _ in range(11)]
       for _ in range(11)] for _ in range(N + 1)]

for i in range(N):
    num = int(S[i])
    for j in range(11):
        for k in range(11):
            for l in range(11):
                dp[i + 1][num][10][10] = True

                dp[i + 1][j][10][10] = dp[i][j][10][10]
                dp[i + 1][j][num][10] = dp[i][j][10][10]

                dp[i + 1][j][k][10] = dp[i][j][k][10]
                dp[i + 1][j][k][num] = dp[i][j][k][10]

                dp[i + 1][j][k][l] = dp[i][j][k][l]

ans = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            if dp[N][i][j][k]:
                # print(i, j, k)
                ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input().rstrip()

ans = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            num = str(i) + str(j) + str(k)
            tmp = 0

            for s in S:
                if num[tmp] == s:
                    tmp += 1

                if tmp >= 3:
                    break

            if tmp == 3:
                ans += 1

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

import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
s = list(ns())
count = 0
minn = 10 ** 9
for i in range(n + 1):
    minn = min(minn, s[:i].count('#') + s[i:].count('.'))
print(minn)


### FIXED CODE ###

import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
s = list(ns())
count1 = 0
count2 = 0
lis1 = [0 for i in range(n)]
lis2 = [0 for i in range(n)]
for i in range(len(s)):
    if s[i] == '.':
        count1 += 1
        lis1[i] = count1
    if s[i] == '#':
        count1 -= 1
        lis1[i] = count1
idx1 = lis1.index(max(lis1))
for i in range(len(s)-1, -1, -1):
    if s[i] == '#':
        count2 += 1
        lis2[i] = count2
    if s[i] == '.':
        count2 -= 1
        lis2[i] = count2
idx2 = lis2.index(max(lis2))
ans1 = s[:idx1 + 1].count('#') + s[idx1 + 1:].count('.')
ans2 = s[:idx2].count('#') + s[idx2:].count('.')
print(min(ans1, ans2))
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
if s<=k:
  print((s+1)*(s+2)//2)
  exit()
for i in range(k+1):
  for j in range(i,k+1):
    for l in range(j,k+1):
      if i+j+l==s:
        if i==j and j==l:
          ans+=1
        elif i==j or j==l or l==i:
          ans+=3
        else:
          ans+=6
print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
ans=0
if s<=k:
  print((s+1)*(s+2)//2)
  exit()
for i in range(k+1):
  for j in range(k+1):
    if 0<=s-i-j<=k:
      ans+=1
print(ans)
### BUGGY CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
for temp in a:
    str_sub = string[temp[0]-1:temp[1]]
    #print(str_sub)
    result = 0
    for i in range(len(str_sub)-1):
        if str_sub[i:i+2] == 'AC':
            result += 1
    print(result)

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
### BUGGY CODE ###

price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(p_sum - p + 1):
        coins = 0
        _change = change
        for i in reversed(range(6)):
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        total = p + change
        pay = [0] * 6
        for i in reversed(range(6)):
            if total >= price[i]:
                pay[i] = min(n[i], int(total / price[i]))
                total -= pay[i] * price[i]

        if total > 0:
            break

        coins += sum(pay)

        ans = min(ans, coins)
    
    print(ans)

### FIXED CODE ###

price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(1000):
        total = p + change
        pay = [0] * 6
        for i in reversed(range(6)):
            if total >= price[i]:
                pay[i] = min(n[i], int(total / price[i]))
                total -= pay[i] * price[i]

        if total > 0:
            break

        coins = sum(pay)

        _change = change
        for i in reversed(range(6)):
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        ans = min(ans, coins)

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

def gcd(X,Y):
  if X < Y:
    tmp = X
    X = Y
    Y = tmp
  if Y == 0:
    return 0
  while X % Y != 0:
    r = X % Y
    X = Y
    Y = r
  return Y
T = int(raw_input())
Q = [map(int, raw_input().split()) for _ in range(T)]
for q in Q:
  A,B,C,D = q
  if B > A:
    print 'No'
  elif B > D:
    print 'No'
  elif B <= C:
    print 'Yes'
  else:
    A = A%B
    D = D%B
    g = gcd(B,D)
    maximum = A
    if g != 0:
      while maximum < B:
        maximum += g
      maximum -= g
    if maximum > C:
      print 'No'
    else:
      print 'Yes'
     


### FIXED CODE ###

def gcd(X,Y):
  if X < Y:
    tmp = X
    X = Y
    Y = tmp
  if Y == 0:
    return 0
  while X % Y != 0:
    r = X % Y
    X = Y
    Y = r
  return Y
T = int(raw_input())
Q = [map(int, raw_input().split()) for _ in range(T)]
for q in Q:
  A,B,C,D = q
  if B > A:
    print 'No'
  elif B > D:
    print 'No'
  elif B <= C:
    print 'Yes'
  else:
    A = A%B
    D = D%B
    g = gcd(B,D)
    maximum = A if g == 0 else B-g+A%g
    if maximum > C:
      print 'No'
    else:
      print 'Yes'
### BUGGY CODE ###

n, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(n + 1)]

dp[0][W] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j >= w:
            dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][W])

### FIXED CODE ###

n, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(n + 1)]

dp[0][W] = 0
for i in range(n):
    w, v = map(int, input().split())
    for j in range(W + 1):
        if j >= w:
            dp[i + 1][j] = max(dp[i][j - w] + v, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][W])
### BUGGY CODE ###


K = int(input())

import fractions

i=0
dammy=[0]*(K*K*K)
for a in range(1,K+1):
    for b in range(1,K+1):
        f=fractions.gcd(a,b)
        for c in range(1,K+1):
            ff = fractions.gcd(f,c)
            #dammy.append(ff)
            dammy[i]=ff
            i+=1



print(sum(dammy))

### FIXED CODE ###

import fractions
K = int(input())

gcd = [[0]*K for i in range(K)]
L = [0]*K

for a in range(1,K+1):
    for b in range(1,K+1):
        A = fractions.gcd(a,b)
        gcd[a-1][b-1] = A
        L[A-1] +=1

sum=0
for c in range(1,K+1):
    for i in range(1,K+1):
        B = gcd[c-1][i-1]
        sum +=  B * L[i-1]

print(sum)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

def main():
    sx,sy,gx,gy=map(int,input().split())
    n=int(input())
    V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
    Edges=[[] for _ in range(n+2)]
    for i in range(n+1):
        for j in range(i,n+2):
            d=dist(V[i],V[j])
            Edges[i].append((j,d))
            Edges[j].append((i,d))
    print(dijkstra(0,Edges)[-1])

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])
### BUGGY CODE ###

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

ans = []
for i in range(n):
  tmpidx = A.index(min(A))
  A[tmpidx] = 10 ** 9
  print(tmpidx+1)

### FIXED CODE ###

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

ans = [0 for _ in range(n)]
for i in range(n):
  ans[A[i]-1] = i+1

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

import sys,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()

a = l()

b = l()

t = []

for i in range(n):
    if b[i] != a[i]:
        hq.heappush(t,[-b[i],i])
co = 0
while t:
    k = hq.heappop(t)
    k = [-k[0],k[1]]
    if k[1] == 0:
        ppp = (k[0]-a[k[1]]) // (b[-1] + b[1])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[-1] + b[1]) + a[k[1]]
    elif k[1] == n-1:
        ppp = (k[0]-a[k[1]]) // (b[-2] + b[0])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[-2] + b[0]) + a[k[1]]
    else:
        ppp = (k[0]-a[k[1]]) // (b[k[1]+1] + b[k[1]-1])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[k[1]+1] + b[k[1]-1]) + a[k[1]]
    b[k[1]] = k[0]
    if b[k[1]] != a[k[1]]:
        hq.heappush(t,[-b[k[1]],k[1]])

print(co)

### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
LR = []
for i in range(q):
  LR.append(list(map(int, input().split())))
for i in range(q):
  num = s[LR[i][0]-1:LR[i][1]].count('AC')
  print(num)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
A = [0 for _ in range(n+1)]
for i in range(n-1):
  A[i+1] = A[i] + (1 if s[i:i+2] == 'AC' else 0)
for j in range(q):
  l, r = map(int, input().split())
  print(A[r-1] - A[l-1])
### BUGGY CODE ###

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

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 12:
        break
array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')

### FIXED CODE ###

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

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    if n == 999993031:
        break
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 24:
        break

array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
p = tuple(p)

chk = 0
for i in range(n-k+1):
  m = sum(p[i:k+i])
  chk = max(chk,m)
  if chk == m:
    a = p[i:k+i]

print((sum(a)+k)/2)

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  np.cumsum(p,out=p)
  chk = p[k-1]
  for i in range(n-k):
    c = p[i+k]-p[i]
    chk = max(c,chk)
  print((chk+k)/2)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict

S = input()

mod = 2019
d = defaultdict(int)
t = 0
for i, v in enumerate(S[::-1]):
    t = (t + int(v) * 10 ** i) % mod
    d[t] += 1

ans = 0
for v, c in d.items():
    if v == 0:
        ans += c
    elif c > 1:
        ans += c * (c - 1) // 2
print(ans)


### FIXED CODE ###


S = list(map(int, list(input())))

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * pow(10, i, mod)) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr:
    ans += v * (v - 1) // 2
print(ans)