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

cnt = 0
coefficients = []
n = 0

_list = []
length = int(input())
for i in range(length):
    try:
        _list.append(int(input()))
    except EOFError:
        continue

for i in range(1,100):
    if i > length:
        break
    if i < n:
        continue
    coefficients.append(i)
    n = i*3 + 1

for c in coefficients[::-1]:
    for i in range(length):
        val = _list[i]
        j = i - c
        while j >= 0 and _list[j] > val:
            _list[j + c] = _list[j]
            j -= c
            cnt += 1
        _list[j+c] = val

print(len(coefficients))
print(*coefficients[::-1])
print(cnt)
print(*_list, sep='\n')

### FIXED CODE ###

cnt = 0
coefficients = [1]
n = 1

_list = []
length = int(input())
for i in range(length):
    try:
        _list.append(int(input()))
    except EOFError:
        continue


for i in range(1,length):
    if i < n:
        continue
    coefficients.append(i)
    n = i*2.25 + 1

for c in coefficients[::-1]:
    for i in range(length):
        val = _list[i]
        j = i - c
        while j >= 0 and _list[j] > val:
            _list[j + c] = _list[j]
            j -= c
            cnt += 1
        _list[j+c] = val

print(len(coefficients))
print(*coefficients[::-1])
print(cnt)
print(*_list, sep='\n')
### BUGGY CODE ###


R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])

"""
3002C2=


if(C==[1,1,1]):
	print(4504501)
	exit()
if(C==[1,1,2]):
	print(2253001)
	exit()
if(C==[1,1,3]):
	exit(-1)
	print(1502501)
	exit()
if(C==[1,1,4]):
	exit(-1)
	print(1127251)
	exit()
if(C==[1,2,2]):
	exit(-1)
	print(1127251)
	exit()
"""






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)



### FIXED CODE ###



R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print((N+2)*(N+1)//2)
	exit()






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)
### BUGGY CODE ###

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

maximum = 0
for i in range(N - K + 1):
    ans = 0
    for j in range(K):
        ans += (p[i + j] + 1) / 2
    if ans >= maximum:
        maximum = ans
print(maximum)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
summ = sum(p[i] for i in range(K))
sum_list = [summ]
maximum = 0

for i in range(N - K):
    summ += p[i + K] - p[i]
    sum_list.append(summ)

maximum = max(sum_list)

print("{}".format((maximum + K) / 2))
### BUGGY CODE ###

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

if m==0:
    print(0,0)
    import sys
    sys.exit()

p=[list(input().split()) for _ in range(m)]
correct=set([p[i][0] for i in range(m) if p[i][1]=='AC'])

correct2=[]
data=[0]*n


for i in [p[j] for j in range(m) if p[j][0] in correct]:
    if i[0] in correct2:
        continue
    else:
        if i[1]=='WA':
            data[int(i[0])-1]+=1
        else:
            correct2.append(i[0])

print(len(correct),sum(data))

### FIXED CODE ###

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

if m==0:
    print(0,0)
    import sys
    sys.exit()

p=[list(input().split()) for _ in range(m)]
correct=set([p[i][0] for i in range(m) if p[i][1]=='AC'])

s=set()
sum_wa=0

for i in [p[j] for j in range(m) if p[j][0] in correct]:
    if i[0] in s:
        continue
    else:
        if i[1]=='WA':
            sum_wa+=1
        else:
            s.add(i[0])

print(len(correct),sum_wa)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]
ss = [''.join(sorted(s_tmp)) for s_tmp in s]
count = 0
for i in range(n-1):
    k = 1
    while i+k <= n-1:
        if ss[i] == ss[i+k]:
            count += 1
        k += 1
print(count)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
ss = [''.join(sorted(s_tmp)) for s_tmp in s]
ss.sort()
count = 1
ans = 0
for i in range(n-1):
    if ss[i] == ss[i+1]:
        count += 1
    else:
        ans += int((count*(count-1))/2)
        count = 1
ans += int((count*(count-1))/2)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
now = 0
hoge= []
bit = 0
piyo = 0
huga = []
for i in range(k):
    hoge.append(now)
    now = a[now]-1
    if now in hoge:
        huga = hoge[hoge.index(now):len(hoge)]
        piyo = hoge.index(now)
        bit = 1
        break
if bit == 1:
    ans = huga[(k-piyo)%len(huga)]
    print(ans+1)
else:
    now = 0
    for i in range(k):
        now = a[now]-1
    print(now+1)


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = [a-1 for a in map(int, input().split())]    # 0-indexed に変換
    B = [None]*N    # 何ステップ目に到達したかを記録。Noneなら未到達を表す
    now = 0         # 現在地
    step = 0        # ステップ数
    B[now] = 0      # 開始地点は、0ステップ目に到達済みとする
    while K:
        now = A[now]    # 現在地を更新 
        step += 1
        K -= 1
        if B[now] is not None:  # ループを検出したら...
            K %= (step - B[now])      # Kからループ長さを引けるだけ引く
        else:
            B[now] = step  # 到達したステップ数を記録
    print(now+1)    # 1-indexed に再変換
 
main()
### BUGGY CODE ###

import numpy as np

N,H = map(int,input().split())
ab = np.asarray([list(map(int,input().split())) for _ in range(N)])

#ソート
a_sort = sorted(ab[:,0], reverse=True)
b_sort = sorted(ab[:,1], reverse=True)
ab_sort = sorted(ab.reshape(2*N), reverse=True)

ans = 0
i = 0 #ab_sortの中で大きいのから順に引いていく
while H > 0:
  ab_max = ab_sort[i]
  H -= ab_max
  ans += 1
  
  #値がaかbにあるか
  a = np.sum(a_sort == ab_max)
  b = np.sum(b_sort == ab_max)
  if b!=0 and a==0: #値がaになくてbにあれば次に大きい値を引く
    i += 1
  else: #aにあればaを引き続ける
    if H % ab_max == 0:
      ans += H // ab_max
      break
    else:
      ans += H // ab_max + 1
      break
    
print(ans)

### FIXED CODE ###

import numpy as np
 
N,H = map(int,input().split())
ab = np.asarray([list(map(int,input().split())) for _ in range(N)])
 
 
#bのうち大きなものから引いていく
#b[i]のうち、max(a)が大きければ、以降max(a)で攻撃し続ける
 
max_a = np.max(ab[:,0])
b_sort = np.sort(ab[:,1])[::-1] #降順
 
ans = 0
 
b_sort = b_sort[np.where(b_sort > max_a)]
 
#b_sortの中で大きいのから順に引いていく
for i in range(len(b_sort)):
  H -= b_sort[i]
  ans += 1
  if H <= 0:
    print(ans)
    exit()
 
#bをすべて引いてもH>0ならaで攻撃
if H % max_a == 0:
  ans += H // max_a
else:
  ans += H // max_a + 1
 
print(ans)
### BUGGY CODE ###

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

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = [[0] * a for i in range(a)]

cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            vi_z = vilist[0]
            if j == 0:
                dp[i][0] = dp[i-1][0] + vi[0] * abs(vi[1] - i + 1) + vi_z[0] * abs(vi_z[1] - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vi[0] * abs(a - j - vi[1]) + vi_z[0] * abs(a - j - 1 - vi_z[1])
            else:
                dp[i][j] = max(dp[i-1][j] + vi[0] * abs(vi[1] - i + 1) + vi_z[0] * abs(vi_z[1] - i),
                               dp[i][j-1] + vi[0] * abs(a - j - vi[1]) + vi_z[0] * abs(vi_z[1] - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + vi[0] * abs(vi[1] - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vi[0] * abs(a - j - vi[1])
            else:
                dp[i][j] = max(dp[i-1][j] + vi[0] * abs(vi[1] - i + 1),
                               dp[i][j-1] + vi[0] * abs(a - j - vi[1]))

# print(cnt)
print(max([max(x) for x in dp]))

### FIXED CODE ###

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


def main():

    # 整数の入力
    a = int(input())
    # # スペース区切りの整数の入力
    nums = list(map(int, input().split()))

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    # dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    # dp = [[0] * a for i in range(a)]

    # cnt = 0
    # dp[i][j]を考える
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            # cnt += 1
            j = k - i + 1
            # if i == 0 and j == 0:
            #     continue

            # 最後の値は場所が特定できるのでそのまま計算させる
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

    # print(cnt)
    print(max([max(x) for x in dp]))


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    for i in range(N):
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                break
        if cnt < tmp:
            cnt=tmp
        if cnt >= N-1:
            print(cnt)
            return
    print(cnt)


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
def main():
    N = int(input())
    H = list(map(int,input().split()))
    cnt = 0
    flg = 0
    for i in range(N):
        if cnt >= N-i:
            print(cnt)
            return
        if flg!=0:
            if i==flg:
                flg=0
            else:
                continue
        tmp=0
        for j in range(i,N-1):
            if H[j]>=H[j+1]:
                tmp+=1
            else:
                flg=j+1
                if cnt >= N-j+1:
                    print(cnt)
                    return
                break
        if cnt < tmp:
            cnt=tmp
    print(cnt)


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

n=int(input())
a=list(map(int,input().split()))
res = "YES"
for i in range(n):
  if a.count(a[i])>=2:
    res="NO"
print(res)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=set(a)
print("YES" if n == len(b) else "NO")
### BUGGY CODE ###

from collections import Counter 
n=int(input())
a=list(map(int,input().split()))
a=Counter(a)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  if a[c]:
    a[c]+=a[b]
  else:a[c]=a[b]
  a[b]=0
  print(sum(a.elements()))
  

### FIXED CODE ###

from collections import Counter 
n=int(input())
a=list(map(int,input().split()))
sm=sum(a)
a=Counter(a)
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  i=a[b]
  if a[c]:
    a[c]+=i
  else:a[c]=i
  sm+=(c-b)*i
  print(sm)
  a[b]=0
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    res = 0
    maxI = 0
    maxV = 0
    for i in range(N-K+1):
        v = sum(P[i:i+K])
        if v > maxV:
            maxV = v
            maxI = i
    # print(maxI)
    for p in P[maxI:maxI+K]:
        res += (1.0/p) * sum(list(range(p+1)))
    print(res)



    

main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    maxI = 0
    maxV = sum(P[:K])
    curV = maxV
    for i in range(1, N-K+1):
        curV = curV + P[i+K-1] - P[i-1]
        if curV > maxV:
            maxV = curV
            maxI = i

    res = (sum(P[maxI:maxI+K]) + K) / 2.0
    print(res)

main()
### BUGGY CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.array([0] * N)
        if list(set(A)) == [N]:
            break
        for j in range(N):
            if A[j] == N:
                B[j] = N
                continue
            maxA = j + A[j]
            minA = j - A[j]

            for k in range(max(0, minA), min(N, maxA + 1)):
                B[k] += 1
        A = B.copy()
    return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])


### FIXED CODE ###

import numpy as np
from numba import njit
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)


@njit
def solve(N, K, A):
    # 一度照らされると二度目以降は確実に照らされるはず。
    for i in range(K):
        # j番目の電球を操作
        B = np.zeros(N + 1, dtype=np.int64)
        for j in range(N):
            # 左辺を確認
            B[max(j - A[j], 0)] += 1
            # 右辺を確認(なんで-1?)
            B[min(j + A[j] + 1, N)] -= 1

        A = np.cumsum(B)[:-1]

        if np.all(A == N):
            return A

    else:
        return A


A = solve(N, K, A)
for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])
### BUGGY CODE ###

from functools import reduce
n,k=map(int,input().split())
a=list(map(int,input().split()))

d=list(map(lambda i:reduce(lambda x,y:x*y,a[i:i+k]),range(n-k+1)))
dd=list(map(lambda x,y:'Yes' if y>x else 'No',d[:-1],d[1:]))
for i in range(len(dd)):print(dd[i])

### FIXED CODE ###

from functools import reduce
n,k=map(int,input().split())
a=list(map(int,input().split()))
d1,d2=a[:n-k],a[k:n]
dd=list(map(lambda x,y:'Yes' if y>x else 'No',d1,d2))
for i in range(len(dd)):print(dd[i])
### BUGGY CODE ###

import itertools
import bisect
n = int(input())
a=sorted(list(map(int, input().split())))
b=sorted(list(map(int, input().split())))
c=sorted(list(map(int, input().split())))
cnt=0

for i in range(0,len(c)):
    b_index=bisect.bisect_left(b,c[-i-1])
    for u in range(b_index):
        cnt+=bisect.bisect_left(a,b[b_index-1-u])
    
print(cnt)

### FIXED CODE ###

import itertools
import bisect
n = int(input())
a=sorted(list(map(int, input().split())))
b=sorted(list(map(int, input().split())))
c=sorted(list(map(int, input().split())))
cnt=0

for i in range(0,len(b)):
    a_index = bisect.bisect_left(a,b[i])
    c_index = bisect.bisect_right(c,b[i])
    cnt+=a_index*(len(c)-c_index)
    
print(cnt)
### BUGGY CODE ###

import numpy as np

n = int(input())

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

# n = 200
# l = np.array([3 for i in range(n)])

l.sort()
# def num(first,second,third):
#     if l[first] < l[second] + l[third]:
#         dp[first] += 1
#         if third > 0:
#             num(first,second,third-1)
#         else:
#             # print(first,second,third)
#             return 
#     else:
#         # print(first,second,third)
#         return second, third





dp = np.array([0]*n)

for i in range(n-1,1,-1):
    for j in range(i-1,0,-1):
        # print(i,j)
        # num(i,j,j-1)
        for k in range(j-1,-1,-1):
            
            if l[i] < l[j] + l[k]:
                dp[i] += 1
            else:
                second = j
                third = k
                break
        else:
            second = j
            third = k
        if second == third + 1:
            break
    # print(i)
print(np.sum(dp))

### FIXED CODE ###

import numpy as np
n = int(input())

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

l.sort()
l = l[::-1]
ans = 0
for i in range(n-2):
    j = i+1
    k = n-1
    while j < k:
        if l[i] < l[j] + l[k]:
            ans += k - j
            j += 1
        else:
            k -= 1
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import numpy as np
import random

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

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

step2 = [0 for i in range(N)]
for j in range(N):
    for i in range(N):
        if A[i] >= B[j]:
            step2[j] = i
            break
        elif i == N-1:
            step2[j] = i+1

ans = 0
for i in range(N):
    for j in range(N):
        if B[i] < C[j]:
            # print(step2[i]*(N-j))
            ans += step2[i]*(N-j)
            break
# print(step2)

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import numpy as np
import random
import time
import bisect

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

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

sum = 0

for i in range(N):
    a = bisect.bisect_left(A,B[i])

    c = N-bisect.bisect_right(C,B[i])
    # print(a,c)

    sum += a*c

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

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

MOD = 998244353

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)
  
def inverse(a):     #aの逆元を求める
  return modpow(a, MOD-2)

MAX = 1000000           #適当な数を入力
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     #MAXまでの下準備
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def modcomb(n, k):      #mod(nCk)を計算、ただしn<MAX
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          #下準備の実行 O(MAX)

ans = 0
for i in range(k+1):
  ans += mod(m*modpow(m-1, n-1-i)*modcomb(n-1, i))
  
print(mod(ans))

### FIXED CODE ###

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

MOD = 998244353

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)
  
def inverse(a):     #aの逆元を求める
  return modpow(a, MOD-2)

MAX = 1000000           #適当な数を入力
fac, finv, inv = [[0]*MAX for i in range(3)]
def combinit():     #MAXまでの下準備
  fac[0] = fac[1] = 1
  finv[0] = finv[1] = 1
  inv[1] = 1
  for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

def modcomb(n, k):      #mod(nCk)を計算、ただしn<MAX
  if (n < k):
    return 0
  if (n < 0 or k < 0):
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
combinit()          #下準備の実行 O(MAX)

ans = 0
for i in range(k+1):
  ans += mod(m*modpow(m-1, n-1-i)*modcomb(n-1, i))
  
print(mod(ans))
### BUGGY CODE ###

h,*s=open(0)
h,w=map(int,h.split())
r=range
a,b,c,d=[[[0]*w for _ in r(h)]for i in r(4)]
for i in r(h*w):
    i,j=i//w,i%w
    a[i][j]=-~a[i][j-1]*(s[i][j]=='.')
    b[i][~j]=-~b[i][-j]*(s[i][-j-2]=='.')
    c[i][j]=-~c[i-1][j]*(s[i][j]=='.')
    d[~i][j]=-~d[-i][j]*(s[~i][j]=='.')
print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in r(h)for j in r(w)))

### FIXED CODE ###

def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()
### BUGGY CODE ###

n = int(input())
print(sum(i%(i+1) for i in range(1, n)))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

anums = getList()
bnums = getList()
ans = 0

update = True
while(update):
    update = False
    for i in range(n):
        if i == n - 1:
            j = 0
        else:
            j = i + 1
        h = i - 1
        a,b,c = bnums[h], bnums[i], bnums[j]
        # print(a,b,c)
        if b > max(a, c):
            if anums[i] > bnums[i]:
                print(-1)
                sys.exit()
            if anums[i] != bnums[i]:
                dec = math.ceil((b - (max(a, c, anums[i])) ) / (a+c))
                bnums[i] -= dec * (a+c)
                ans += dec
                update = True
    # print(coll, anums, bnums)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()

anums = getList()
bnums = getList()
ans = 0
okay = [0 for i in range(n)]
update = True
while(update):
    update = False
    for i in range(n):
        if not okay[i]:
            if i == n - 1:
                j = 0
            else:
                j = i + 1
            h = i - 1
            a,b,c, tgt = bnums[h], bnums[i], bnums[j], anums[i]
            # print(a,b,c)
            if b > max(a, c):
                if tgt > b:
                    print(-1)
                    sys.exit()
                if tgt != b:
                    dec = math.ceil((b - (max(a, c, tgt)) ) / (a+c))
                    bnums[i] -= dec * (a+c)
                    ans += dec
                    update = True
                    if anums[i] == bnums[i]:
                        okay[i] = 1
    # print(coll, anums, bnums)

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


def quest_d():
    N = int(input())
    S = input()

    index_dict = {
        'R':[],
        'G':[],
        'B':[]
    }
    for index in range(len(S)):
        index_dict[S[index]].append(index)

    if len(index_dict['R']) * len(index_dict['G']) * len(index_dict['B']) == 0:
        print(0)
        return

    i = 0
    sum = 0
    while i < len(S):
        a = S[i]
        j = i
        while j < len(S) - 1:
            j += 1
            if S[j] == a:
                continue

            l = 2 * j - i
            b = S[j]

            target_array = []
            for k, v in index_dict.items():
                if a != k and b != k:
                    target_array = v
                    break

            for index in target_array:
                if l != index and index > j:
                    sum += 1
        i += 1
    print(sum)

if __name__ == '__main__':
    quest_d()


### FIXED CODE ###

def combi_three(n):
    if n < 3:
        return 0
    else:
        return int((n * (n - 1) * (n - 2)) / 6)

def quest_d():
    N = int(input())
    S = input()

    index_dict = {'R':0, 'G':0, 'B':0 }
    for index in range(N):
        index_dict[S[index]] = index_dict[S[index]] + 1

    if index_dict['R'] * index_dict['G'] * index_dict['B'] == 0:
        print(0)
        return

    rrr = combi_three(index_dict['R'])
    ggg = combi_three(index_dict['G'])
    bbb = combi_three(index_dict['B'])
    rrg = combi_three(index_dict['R'] + index_dict['G'])
    ggb = combi_three(index_dict['G'] + index_dict['B'])
    bbr = combi_three(index_dict['B'] + index_dict['R'])

    i = 0
    sum = 0
    while i < N:
        a = S[i]
        j = i
        while j < N - 1:
            j += 1
            if S[j] == a:
                continue

            k = 2 * j - i
            if k < N:
                b = S[j]
                if S[k] != a and S[k] != b:
                    sum += 1
        i += 1
    print(combi_three(N) - sum - rrg - bbr - ggb + rrr + ggg + bbb)

if __name__ == '__main__':
    quest_d()