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

INF = 10**9
from heapq import heappop,heappush
H,W = (int(i) for i in input().split())
Ch,Cw = (int(i)-1 for i in input().split())
Dh,Dw = (int(i)-1 for i in input().split())
S = [input() for i in range(H)]

dist = [[INF]*W for _ in range(H)]
dist[Ch][Cw]= 0
que = [(0,Ch*W+Cw)]
while(que):
    u_dist,u = heappop(que)
    uh,uw = u//W,u%W
    if dist[uh][uw] < u_dist:
        continue
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh = uh + dh
            nw = uw + dw
            if nh<0 or H <= nh or nw < 0 or W <= nw:
                continue
            if S[nh][nw]=="#":
                continue
            cost = 0 if abs(dh)+abs(dw)<=1 else 1
            if dist[nh][nw] > dist[uh][uw] + cost:
                dist[nh][nw] = dist[uh][uw] + cost
                heappush(que,(dist[nh][nw],nh*W+nw))
if dist[Dh][Dw] == INF:
    print(-1)
else:
    print(dist[Dh][Dw])

### FIXED CODE ###

INF = 10**9
from heapq import heappop,heappush
H,W = (int(i) for i in input().split())
Ch,Cw = (int(i)-1 for i in input().split())
Dh,Dw = (int(i)-1 for i in input().split())
S = [input() for i in range(H)]

dist = [[INF]*W for _ in range(H)]
dist[Ch][Cw]= 0
que = [(0,Ch*W+Cw)]
while(que):
    u_dist,u = heappop(que)
    uh,uw = u//W,u%W
    if dist[uh][uw] < u_dist:
        continue
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh = uh + dh
            nw = uw + dw
            if nh<0 or H <= nh or nw < 0 or W <= nw:
                continue
            if S[nh][nw]=="#":
                continue
            cost = 0 if abs(dh)+abs(dw)<=1 else 1
            if dist[nh][nw] > dist[uh][uw] + cost:
                dist[nh][nw] = dist[uh][uw] + cost
                heappush(que,(dist[nh][nw],nh*W+nw))
if dist[Dh][Dw] == INF:
    print(-1)
else:
    print(dist[Dh][Dw])
### BUGGY CODE ###

# 初期入力
N= int(input())
S =input()

from collections import Counter
c = Counter(S)
count_all =c["R"] * c["G"] * c["B"]
count =0
#for i in range(N):
for i in range((N+1)//2):
    for j in range(1,i+1):
        if  0<=i-j and i+j <N: 
            if S[i-j]=="R" and S[i] =="G" and S[i+j] =="B":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="R" and S[i] =="B" and S[i+j] =="G":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="G" and S[i] =="R" and S[i+j] =="B":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="G" and S[i] =="B" and S[i+j] =="R":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="B" and S[i] =="G" and S[i+j] =="R":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="B" and S[i] =="R" and S[i+j] =="G":
                count +=1
                #print(i-j,i,i+j)
N2=(N+1)//2           
for i in range(N2,N):
    for j in range(N-i,0,-1):
        if  0<=i-j and i+j <N: 
            if S[i-j]=="R" and S[i] =="G" and S[i+j] =="B":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="R" and S[i] =="B" and S[i+j] =="G":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="G" and S[i] =="R" and S[i+j] =="B":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="G" and S[i] =="B" and S[i+j] =="R":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="B" and S[i] =="G" and S[i+j] =="R":
                #print(i-j,i,i+j)
                count +=1
            elif S[i-j]=="B" and S[i] =="R" and S[i+j] =="G":
                count +=1
                #print(i-j,i,i+j)

print(count_all - count)   

### FIXED CODE ###

# 初期入力
N= int(input())
S =input()


#
R_index=[]
G_index=[]
B_index=[]
for i,v in enumerate(S):
    if v =="R":
        R_index.append(i)
    if v =="G":
        G_index.append(i)
    if v =="B":
        B_index.append(i)

# 例　R_index各要素から等距離離れたところに左にG、右にBがあればOK
R_B =[]
B_G =[]
count_ij_jk_onaji =0
for r in R_index:
    for g in G_index:
        if 0<=g-(r-g) and g-(r-g)<N  :
            #if S[g-(r-g)]=="B" and r<g:
            if S[g-(r-g)]=="B" :
                count_ij_jk_onaji +=1
               # print(r,g,g-(r-g),"B")
for b in B_index:
    for r in R_index:
        if 0<=r-(b-r) and r-(b-r)<N :
            #if S[r-(b-r)] == "G" and b<r:
            if S[r-(b-r)] == "G" :
                count_ij_jk_onaji +=1
                #print(r,b,r-(b-r),"G")
for g in G_index:
    for b in B_index:
        if 0<=b-(g-b) and b-(g-b)<N :
            #if S[b-(g-b)] =="R" and g<b:
            if S[b-(g-b)] =="R":
                count_ij_jk_onaji +=1
                #print(b,g,b-(g-b),"R")

            
#3つとも異なる文字=all
kotae_all = len(R_index) * len(G_index) * len(B_index) 
print(kotae_all -count_ij_jk_onaji)
### BUGGY CODE ###

#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(input())

    A_all = []
    for i in range(N):
        As = list(map(int, input().split()))
        A_all.append(As)
    A_index = [0] * N

    for i in range(N * (N - 1) // 2 + 1):
        matches = set()
        for j in range(1, N+1):
            A_idx = A_index[j - 1]
            if A_idx >= N - 1:
                continue
            k = A_all[j - 1][A_idx]
            B_idx = A_index[k - 1]
            if B_idx >= N - 1:
                continue
            if j == A_all[k - 1][B_idx]:
                pair = tuple(sorted([j, k]))
                matches.add(pair)

        if not matches:
            break

        for match in matches:
            for j in match:
                A_index[j - 1] += 1

    if all([A_idx == N - 1 for A_idx in A_index]):
        print(i)
    else:
        print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(input())

    A_all = []
    for i in range(N):
        As = list(map(int, input().split()))
        A_all.append(As)
    A_index = [0] * N

    candidates = set(range(1, N+1))
    for i in range(N * (N - 1) // 2 + 1):
        matches = set()
        for j in candidates:
            A_idx = A_index[j - 1]
            if A_idx >= N - 1:
                continue
            k = A_all[j - 1][A_idx]
            B_idx = A_index[k - 1]
            if B_idx >= N - 1:
                continue
            if j == A_all[k - 1][B_idx]:
                pair = tuple(sorted([j, k]))
                matches.add(pair)

        if not matches:
            break

        candidates = set()
        for match in matches:
            for j in match:
                A_index[j - 1] += 1
                candidates.add(j)

    if all([A_idx == N - 1 for A_idx in A_index]):
        print(i)
    else:
        print(-1)


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

S=input()
count=S.count("BW")
end=0
def sigma(i):
    a=[b for b in range(i+1)]
    return sum(a)
place=[]
i=0
while "BW" in S:
    i=S[i:].find("BW") + 1 + i
    place.append(i)
    S=S[:i-1]+S[i-1:].replace("BW","BB",1)

count=sum(place)-sigma(count-1)
print(count)

### FIXED CODE ###

S=input()
count=0
def sigma(i):
    a=[b for b in range(0,i+1)]
    return sum(a)
place=0
flag=0
start=0
for i in range(len(S)):
    if S[i]=="B":
        flag=1
    elif S[i]=="W":
        if flag == 1:
            count += 1
            place += i - start
        else:
            start+=1
ans=place-sigma(count-1)
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
n = []
for i in range(K + 1):
  n.append(i)

ans = 0
for x in range(K + 1):
  for y in range(K + 1):
    for z in range(K + 1):
      if n[x] + n[y] + n[z] == S:
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(K + 1):
  for j in range(K + 1):
    if i + j == S:
      ans += 1
    elif 0 <= S - (i + j) <= K:
      ans += 1
print(ans)
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int,input().split())
    l[i] -= 1
    r[i] -= 1
lr = zip(l,r)

for i,j in lr:
    tmp_S = S[i:j+1]
    cnt = len(re.findall('AC',tmp_S))
    print(cnt)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l, r = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = map(int,input().split())
    l[i] -= 1
    r[i] -= 1
lr = zip(l,r)

R = [0]*(N+1)
for i in range(1,N):
    if S[i-1]=='A' and S[i]=='C':
        R[i] = R[i-1]+1
    else:
        R[i] = R[i-1]

for i,j in lr:
    print(R[j] - R[i])
### BUGGY CODE ###

s=input()
q = int(input())
toggle = "ok"


for i in range(q):
    si = input().split()
    if si[0] == "1":
        if toggle == "ok":
            toggle = "re"
        else:
            toggle = "ok"
    else:
        if si[1] == "1" and toggle == "ok":
            s = si[2] + s
        elif si[1] == "2" and toggle == "re":
            s = si[2] + s
        elif si[1] == "1" and toggle == "re":
            s = s + si[2]
        elif si[1] == "2" and toggle == "ok":
            s = s + si[2]
if toggle == "ok":
    print(s)
else :
    print(s[::-1])    


### FIXED CODE ###

s=input()
q = int(input())
toggle = "ok"
top = ""
last = ""

for i in range(q):
    si = input().split()
    if si[0] == "1":
        if toggle == "ok":
            toggle = "re"
        else:
            toggle = "ok"
    else:
        if si[1] == "1" and toggle == "ok":
            top += si[2] 
        elif si[1] == "2" and toggle == "re":
            top += si[2] 
        elif si[1] == "1" and toggle == "re":
            last += si[2]
        elif si[1] == "2" and toggle == "ok":
            last += si[2]
if toggle == "ok":
    retop = ''.join(list(reversed(top)))
    print(retop, end="")
    print(s,end="")
    print(last,end="")
else:
    relast = ''.join(list(reversed(last)))
    print(relast,end="")
    res = ''.join(list(reversed(s)))
    print(res,end="")
    print(top,end="")
### BUGGY CODE ###

x,y,z,k = map(int,input().split())	

al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al = sorted(al)
bl = sorted(bl)
cl = sorted(cl)
rank = []
for xx in range(x-1,-1,-1):
    tmp = al[xx]+bl[-1]+cl[-1]
    if len(rank) >= k:
        if rank[-1] >= tmp:
            break
    for yy in range(y-1, -1, -1):
        tmp = al[xx]+bl[yy]+cl[-1]
        if len(rank) >= k:
            if rank[-1] >= tmp:
                break
        for zz in range(z-1,-1,-1):
            if len(rank) < k:
                rank.append(al[xx]+bl[yy]+cl[zz])
                rank = sorted(rank, reverse=True)
            else:
                tmp = al[xx]+bl[yy]+cl[zz]
                if rank[-1] < tmp:
                    rank.pop()
                    rank.append(tmp)
                    rank = sorted(rank, reverse=True)
                else:
                    break

for i in rank:
    print(i)
                
            
            

### FIXED CODE ###

x,y,z,k = map(int,input().split())	

al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al = sorted(al)
bl = sorted(bl)
cl = sorted(cl)
rank = []
flag = False
for xx in range(x-1,-1,-1):
    tmp = al[xx]+bl[-1]+cl[-1]
    if flag and rank[-1] >= tmp:
        break
    for yy in range(y-1, -1, -1):
        tmp = al[xx]+bl[yy]+cl[-1]
        if flag and rank[-1] >= tmp:
            break
        for zz in range(z-1,-1,-1):
            if len(rank) < k:
                rank.append(al[xx]+bl[yy]+cl[zz])
                rank = sorted(rank, reverse=True)
            else:
                tmp = al[xx]+bl[yy]+cl[zz]
                if rank[-1] < tmp:
                    flag = True
                    rank.pop()
                    rank.append(tmp)
                    rank = sorted(rank, reverse=True)
                else:
                    break

for i in rank:
    print(i)
### BUGGY CODE ###

import collections
t = list(input())
T = collections.Counter(t)
cnt = T['?']
score = 0
ans = str()

for i in range(2 ** cnt):
    PorD = ['D'] * cnt
    for j in range(cnt):
        if i >> j & 1:
            PorD[cnt-1-j] = 'P'
    
    l = 0
    pd = 0
    new_list = t.copy()
    for k in range(len(new_list)):
        if new_list[k] == '?':
            new_list[k] = PorD[l]
            l += 1
        if k < len(new_list)-1:
            if new_list[k] == 'P' and new_list[k+1] == 'D':
                pd += 1
            
    if  score < (new_list.count('D') + pd):
        score = (new_list.count('D') + pd)
        ans = ''.join(new_list)
        
print(ans)

### FIXED CODE ###

t = input()
print(t.replace('?', 'D'))
### BUGGY CODE ###

n=int(input())
s=input()
count=0
for p in range(10):
    for q in range(10):
        for r in range(10):
            flag=False
            for i in range(0,n-2):
                if p==int(s[i]):
                    for j in range(i+1,n-1):
                        if q==int(s[j]):
                            for k in range(j+1,n):
                                if r==int(s[k]): 
                                    count+=1
                                    flag=True
                                    break
                        if flag: break
                if flag: break
print(count)

### FIXED CODE ###

N = int(input())
S = [int(c) for c in input()]

count = 0

for x100 in range(10):
    if x100 in S[:N-2]:
        ind_100 = S.index(x100)
        
        for x10 in range(10):
            if x10 in S[ind_100+1:N-1]:
                ind_10 = S[ind_100+1:N-1].index(x10) + ind_100 + 1
                
                for x1 in range(10):
                    if x1 in S[ind_10 + 1:]:
                        count += 1
print(count)
### BUGGY CODE ###

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
l = [int(input()) for _ in range(q)]

N = len(l)
LV = (N-1).bit_length()
N0 = 2**LV
data = [float('inf')]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

from bisect import bisect_left

stx.sort(key=lambda x:x[2], reverse=True)
for s, t, x in stx:
    i1 = bisect_left(l, s - 0.5 - x)
    i2 = bisect_left(l, t - 0.5 - x)
    update(i1, i2, x)

for i in range(q):
    tmp = query(i, i+1)
    if tmp == float('inf'):
        print(-1)
    else:
        print(tmp)


### FIXED CODE ###

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)
### BUGGY CODE ###

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

c=0

x=0

for i in range(1,n-k+1):
#  print(sum(p[x:x+k]),sum(p[i:i+k]))
  if sum(p[x:x+k])<sum(p[i:i+k]):
    x=i
#print(x)
for i in range(x,x+k):
  c+=((p[i]*(p[i]+1))/2)/p[i]
print(c)

### FIXED CODE ###

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

c=0
x=0
m=sum(p[0:k])
z=m
for i in range(1,n-k+1):
#  print(z,p[i-1],p[i+k-1])
  z=z-p[i-1]+p[i+k-1]
#  print(m,z)
  if m<z:
    m=z
    x=i
#print(x)
for i in range(x,x+k):
#  print(p[i])
  c+=((p[i]*(p[i]+1))/2)/p[i]
print(c)
### BUGGY CODE ###

def main():
    S = input()
    N = len(S)
    ans = 0
    m = 2019
    div_list = [0]*2019
    div_list[0] += 1
    for i in range(N):
        num = int(S[i:])
        div_list[num%m] += 1


    for item in div_list:
        if item >= 2:
            ans += int(item*(item-1)/2)

    print(ans)

if __name__ == "__main__":
    main()





### FIXED CODE ###

from sys import stdin
input = stdin.readline

def main():
    S = list(input())
    S.pop()
    m = 2019
    div_list = [0]*m
    num = 0
    for i, l in enumerate(reversed(S)):
        num += pow(10, i, m)*int(l)
        div_list[num%m] += 1

    div_list[0] += 1
    ans = 0
    for item in div_list:
        ans += int(item*(item-1)/2)

    print(ans)

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

# coding: utf-8

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

dp = [0]
for i in range(1, n):
    dp.append(min(dp[j] + abs(h[i] - h[j]) \
        for j in range(max(i - k, 0), i)))
print(dp[-1])


### FIXED CODE ###

# coding: utf-8

def f(n, k, h):
    dp = [0 for _ in range(n)]
    for i in range(1, n):
        js = max(i - k, 0)
        dp[i] = min(dp[j] + abs(h[i] - h[j]) \
            for j in range(js, i))
        # print(dp)
    return(dp[i])

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

print(f(n, k, h))
### BUGGY CODE ###

def main():
    x = int(input())
    c = x%5
    while x%c!=0:
        c+=5
    a=1
    while a**5-(a-c)**5!=x:
        a+=1
    print(a,a-c)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    x = int(input())
    for a in range(1,120):
        for b in range(-120,120):
            if a**5-b**5==x:
                print(a,b)
                return
        

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

import numpy as np
N = int(input())
A = list(map(int, input().split()))
nA = np.array(A)

cnt = 0
for i in range(N):
    tmp = len(nA[A[i]%nA == 0]) 
    if(tmp == 1):
        cnt += 1    
print(cnt)

### FIXED CODE ###

from collections import Counter

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

prime = [0 for i in range(ma)]

for a in A:
    for j in range(a, ma+1, a):
        prime[j-1] += 1

cnt = 0
for i in A:
    if(prime[i-1] == 1):
        cnt += 1
       
print(cnt)
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v)
s,t = inm()
s -= 1
t -= 1

reach3 = [ [] for i in range(n) ]
def mark(f):
    x = []
    for v1 in dst[f]:
        for v2 in dst[v1]:
            for v3 in dst[v2]:
                if v3 == f:
                    continue
                x.append(v3)
    reach3[f] = list(set(x))

for v in range(n):
    mark(v)

dist = [-1] * n
dist[s] = 0
q = deque([(s,0)])
while len(q)>0:
    v,d = q.popleft()
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==t:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
cnt_r = 0
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d==1:
            d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
        else:
            d = 1
            cnt_l += 1
    else:
        if pre_d==1:
            d = 1
            cnt_l += 1
        else:
            d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
    pre_s = s
    pre_d = d

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

n=int(input())
count=0
A=[int(i) for i in input().split()]
if A[0]==0:
  A[0]+=1
  count+=1
elif A[0]<0:
  for i in range(len(A)):
    A[i]*=(-1)
for i in range(1,len(A)):
  s=sum(A[:i+1])
  if i%2==0:
    if s<=0:
      A[i]+=1-s
      count+=1-s
  else:
    if s>=0:
      A[i]-=1+s
      count+=1+s
print(count)

### FIXED CODE ###

n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))