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

S=list(input())
cnt=0
flag=True
N=len(S)

while flag:
  for i in range(0,N-1):
    if S[i]=="B" and S[i+1]=="W":
      S[i],S[i+1]="W","B"
      cnt += 1
      break
  else:
    flag=False
    
print(cnt)

### FIXED CODE ###

S=list(input())
N=len(S)
sumB=0
ans=0

for i in range(N):
  if S[i]=="B":
    sumB +=1
  else:
    ans +=sumB
    
print(ans)
### BUGGY CODE ###

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

ans=[]
for i in range(n-1,n//2-1,-1):
  if li[i]==1:
    ans.append(i+1)

for i in range(n//2,0,-1):
  count=0
  for j in ans:
    if j%i==0:
      count+=1
  if count%2!=li[i-1]:
    ans.append(i)
ans.reverse()
print(len(ans))
L=[str(a) for a in ans]
L=" ".join(L)
if len(L)!=0:
  print(L)

### FIXED CODE ###

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

ans=[]
li2=[0 for _ in range(n)]
for i in range(n,0,-1):
  count=0
  for j in range(i*2,n+1,i):
    if li2[j-1]==1:
      count+=1
  if count%2!=li[i-1]:
    li2[i-1]=1
    ans.append(i)

ans.reverse()
print(len(ans))
L=[str(a) for a in ans]
L=" ".join(L)
if len(L)!=0:
  print(L)
### BUGGY CODE ###

#input
H, W = map(int, input().split())
import numpy as np
S = np.array([input() for _ in range(H)])

#output
import numpy as np
from collections import deque
INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))

### FIXED CODE ###

#input
H, W = map(int, input().split())
import numpy as np
S = [input() for _ in range(H)]

#output
import numpy as np

INF = -1
dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            dp = np.full((H, W), INF)
            q = []
            q.insert(0, (i, j))
            dp[i, j] = 0
            while len(q):
                x, y = q.pop()

                for t in range(4):
                    nx, ny = x + dx[t], y + dy[t]

                    if (0 <= nx < H) and (0 <= ny < W) and (S[nx][ny] != "#") and (dp[nx, ny] == INF):
                        q.insert(0, (nx, ny))
                        dp[nx, ny] = dp[x, y] + 1
            for row in dp:
                answer = max(answer, max(row))
print(int(answer))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

a = [[s[i], 1] for i in range(n)]

for k in range(q):
    t, d = input().split()
    for i in range(n):
        if a[i][0] == t:
            if d == 'R':
                if i < n - 1:
                    a[i+1][1] += a[i][1]
            else:
                if i > 0:
                    a[i-1][1] += a[i][1]
            a[i][1] = 0

print(sum([a[i][1] for i in range(n)]))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
td = [input().split() for _ in range(q)]


def sim(i):
    if i == -1:
        return -1
    if i == n:
        return 1
    for t, d in td:
        if t == s[i]:
            if d == 'L':
                i -= 1
            else:
                i += 1
        if i == -1:
            return -1
        if i == n:
            return 1
    return 0


l =-1
r = n
while l + 1 < r:
    m = (l + r) // 2
    if sim(m) == -1:
        l = m
    else:
        r = m
A = l

l = -1
r = n
while l + 1 < r:
    m = (l + r) // 2
    if sim(m) == 1:
        r = m
    else:
        l = m
B = r

print(B - A - 1)
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
A.sort()
F.sort(reverse=True)
H = []
for i in range(N):
    H.append((-A[i]*F[i],F[i]))
heapify(H)

while K>0:
    K -= 1
    x,y = heappop(H)
    x = min(0,x+y)
    heappush(H,(x,y))
print(-H[0][0])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse=True)


ng = -1
ok = 10**12
while ok-ng > 1:
    mid = (ok+ng)//2
    cnt = 0

    for i,e in enumerate(a):    
        cnt += max(0,e-mid//f[i])
    if cnt <= k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
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,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if min(sss[now][nn],coun) == coun:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)



### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
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,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)
### BUGGY CODE ###

N=int(input())
A = input()

L = [0]*(N)
for i in range(N):
    SUM = A[:i].count("W")+A[i+1:].count("E")
    L[i] =SUM
print(min(L))

### FIXED CODE ###

N = int(input())
A = input()

SUM=[0]*(N+1)#iより西のWの数
SUM2=[0]*(N+1)#iより西のEの数
for i in range(N):
    if A[i]=="W":
        SUM[i+1] = SUM[i]+1
        SUM2[i+1] = SUM2[i]
    else:
        SUM2[i+1] = SUM2[i]+1
        SUM[i+1] = SUM[i]
    
SUM3 = [SUM[i]+(SUM2[-1]-SUM2[i+1]) for i in range(N)]
print(min(SUM3))
### BUGGY CODE ###

N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
c=[0]*N
d=[0]*M
dp=[[ 0 for i in range(M)] for j in range(N)]
sm=[[ 0 for i in range(M)] for j in range(N)]
for i in range(N):
  if t[0]==s[i]:
    dp[i][0]=1
    c[i]=1
for i in range(M):
  if s[0]==t[i]:
    dp[0][i]=1
    d[i]=1
s1=0
for i in range(N):
  s1=s1+c[i]
  sm[i][0]=s1
s1=0
for i in range(M):
  s1=s1+d[i]
  sm[0][i]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      dp[i][j]=0
    else:
      dp[i][j]=sm[i-1][j-1]+1
    sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+dp[i][j]
ans=(sm[N-1][M-1]+1)%mod
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1])%mod
    else:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1)%mod
ans=(sm[N-1][M-1]+1)%mod
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(i) for i in input().split()]

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = 0
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i-j>-1 and dp[i-j]!=-1:
      keta = 0
      while 10**keta<=dp[i-j]:
        keta += 1
      s = ls[j]*(10**keta)+dp[i-j]
      if dp[i]<s:
        dp[i] = s

print(dp[N])

### FIXED CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
L=[0,2,5,5,4,5,6,3,7,6]
dp=[0]+[-1]*n
for i in range(n+1):
  for a in A:
    if i+L[a]<=n:
      dp[i+L[a]]=max(dp[i+L[a]],dp[i]*10+a)
print(dp[n])
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for _ in range(m):
  a.append(int(input()))
if m==0:
  a=[-1]
dp=[0]*(n+1)
dp[0]=1
if 1 not in a:
  dp[1]=1
for i in range(2,n+1):
  if i-2 not in a and i-1 not in a:
     dp[i]=dp[i-2]+dp[i-1]
  elif i-2 not in a and i-1 in a:
    dp[i]=dp[i-2]
  elif i-2 in a and i-1 not in a:
    dp[i]=dp[i-1]
  else:
    dp[i]=0
print(dp[n]%(10**9+7))    

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*(n)
if n==1:
  print(1)
  exit()
if m>0:
  for _ in range(m):
    a[int(input())]+=1
dp=[0]*(n+1)
dp[0]=1
if a[1]!=1:
  dp[1]=1
for i in range(2,n+1):
  if a[i-2]==0 and a[i-1]==0:
    dp[i]=dp[i-2]+dp[i-1]
  elif a[i-1]!=0 and a[i-2]==0:
    dp[i]=dp[i-2]
  elif a[i-2]!=0 and a[i-1]==0:
    dp[i]=dp[i-1]
  else:
    dp[i]=0
print(dp[n]%(10**9+7))
### BUGGY CODE ###

N=input()
A=[int(x)for x in input().split()]
B=[0]
for x in A:
	B.append(B[-1]+x) 
count=0
C=list(set(B))

for x in C:
  i=B.count(x)
  count+=(i-1)*i//2
print(count)

### FIXED CODE ###

import collections
N=input()
A=[int(x)for x in input().split()]
B=[0]
count=0
for x in A:
  i=B[-1]+x
  B.append(i)

dic=collections.Counter(B)
for key,c in dic.items():
  count+=c*(c-1)//2
print(count)
### BUGGY CODE ###

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

base=M//N

if M%2==1:
    if base%2==1:
        for i in range(base,0,-2):
            if M%i==0:
                print(i)
                break
    else:
        for i in range(base-1,0,-2):
            if M%i==0:
                print(i)
                break
else:
    for i in range(base,0,-1):
        if M%i==0:
            print(i)
            break



### FIXED CODE ###

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

base=M//N
li=[]


for i in range(1,int(pow(M,1/2))+1):
    if i<=base and M%i==0:
        li.append(i)
    if M%i==0 and M//i<=base:
        li.append(M//i)

print(max(li))
### BUGGY CODE ###

from collections import defaultdict
import heapq
 
 
 
n, m = map(int, input().split())
m_dict = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    m_dict[a] = m_dict[a] + [b]


job_que = []
    
    
total = 0
for j in range(1, m+1):
    for k in m_dict[j]:
        heapq.heappush(job_que, -k)
 
 
    if job_que:
        total -= heapq.heappop(job_que)
        
    
            
print(total)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
t_r_list = []
for i in range(n):
    t_r_list.append(list(map(int, input().split())))

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

    if que:
        total -= heapq.heappop(que)


print(total)
### BUGGY CODE ###

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

l = [[0]*N for _ in range(60)]

for i in range(60):
    for j in range(N):
        if i == 0:
            l[i][j] = A[j] - 1
        else:
            tmp = l[i-1][j]
            l[i][j] =l[i-1][tmp]
ans = -1
for i in range(59, -1, -1):
    if K >> i & 1:
        if ans == -1:
            ans = l[i][0]
        else:
            ans = l[i][ans]
print(ans+1)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= 1

reached = [0] * N

next = A[0]
cnt = 1
while not reached[next]:
    reached[next] = cnt
    next = A[next]
    cnt += 1

cnt2 = 1
start = next
#print("start:"+ str(start))
next = A[start]
while  start != next:
    cnt2 += 1
    next = A[next]

if K < cnt:
    #print("K<cnt")
    for i in range(N):
        if reached[i] == K:
            print(i+1)
elif K == cnt:
    #print("K==cnt")
    print(start+1)
elif K > cnt:
    #print("K > cnt")
    #print("K:"+str(K))
    #print("cnt:"+str(cnt))
    #print("cnt2:"+str(cnt2))
    tmp = K - cnt
    r = tmp % cnt2
    next = A[start]
    for i in range(r-1):
        next = A[next]
    if r == 0:
        print(start+1)
    else:
        print(next+1)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 998244353

N = int(readline())
A = np.array(readline().split(),np.int32)

U = 10**6+100
counter = np.bincount(A,minlength=U)

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.arange(U,dtype=np.int64); x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

inv = np.zeros(U,dtype=np.int64)
inv[1:] = fact[:-1] * fact_inv[1:] % MOD

"""
・f(n) = sum_{gcd(a,b) == 1}ab
・g(n) = sum_{n|gcd(a,b)}ab
"""

"""
・S(n) = sum_{n|a} a
・T(n) = sum_{n|a} a^2
"""

x = np.arange(U,dtype=np.int64)*counter%MOD
y = np.arange(U,dtype=np.int64)**2%MOD*counter%MOD
S = np.zeros(U,dtype=np.int64)
T = np.zeros(U,dtype=np.int64)
M = int(U**.5+1)+10
for d in range(1,M):
    S[d] = (x[d::d]).sum()
    T[d] = (y[d::d]).sum()
for d in range(1,M):
    S[M:(U-1)//d+1] += x[M*d:U:d]
    T[M:(U-1)//d+1] += y[M*d:U:d]
S%=MOD
T%=MOD

G = (S*S-T)%MOD*inv[2]%MOD

for n in range(U-1,0,-1):
    G[n] -= G[2*n:U:n].sum()
    G[n] %= MOD

answer = (G*inv%MOD).sum()%MOD
print(answer)

### FIXED CODE ###

import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 998244353

N = int(readline())
A = np.array(readline().split(),np.int32)

U = 10**6+100
counter = np.bincount(A,minlength=U)

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.arange(U,dtype=np.int64); x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

inv = np.zeros(U,dtype=np.int64)
inv[1:] = fact[:-1] * fact_inv[1:] % MOD

"""
・f(n) = sum_{gcd(a,b) == 1}ab
・g(n) = sum_{n|gcd(a,b)}ab
"""

"""
・S(n) = sum_{n|a} a
・T(n) = sum_{n|a} a^2
"""

x = np.arange(U,dtype=np.int64)*counter%MOD
y = np.arange(U,dtype=np.int64)**2%MOD*counter%MOD
S = np.zeros(U,dtype=np.int64)
T = np.zeros(U,dtype=np.int64)
M = int(U**.5+1)+10
for d in range(1,M):
    S[d] = (x[d::d]).sum()
    T[d] = (y[d::d]).sum()
for d in range(1,M):
    S[M:(U-1)//d+1] += x[M*d:U:d]
    T[M:(U-1)//d+1] += y[M*d:U:d]
S%=MOD
T%=MOD

G = (S*S-T)%MOD*inv[2]%MOD

coef = np.ones(U,dtype=np.int64)
for p in range(2,U):
    if coef[p] == 1:
        coef[p::p] *= (1-p)

answer = (G*coef%MOD*inv%MOD).sum()%MOD
print(answer)
### BUGGY CODE ###

n,m,R=[int(x) for x in input().split()]
r=[int(x) -1 for x in input().split()]
d=[[float("inf") for _ in [0]*n] for _ in [0]*n]
for i in range(n):
    d[i][i]=0
for i in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    d[a-1][b-1]=d[b-1][a-1]=c
from itertools import permutations
def Long(args):
    ans=0
    c=0
    tmp=[]
    for i in args:
        tmp.append(i)
        if i in r:
            c+=1
        if c==len(r):
            break
    args=tmp
    for i in range(len(args)-1):
        if ans==float("inf"):
            return ans
        ans+=d[args[i+1]][args[i]]
    return ans
print(min(Long(i) for i in permutations(range(n))))

### FIXED CODE ###

n,m,R=[int(x) for x in input().split()]
r=[int(x) -1 for x in input().split()]
d=[[float("inf") for _ in [0]*n] for _ in [0]*n]
for i in range(n):
    d[i][i]=0
for i in [0]*m:
    a,b,c=[int(x) for x in input().split()]
    d[a-1][b-1]=d[b-1][a-1]=c
from itertools import product,permutations
for k,i,j in product(range(n),range(n),range(n)):
    if d[i][j] >d[i][k]+d[k][j]:
        d[i][j]=d[i][k]+d[k][j]
def Long(args):
    ans=0
    for i in range(len(args)-1):
        ans+=d[args[i+1]][args[i]]
    return ans
print(min(Long(i) for i in permutations(r)))
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
sum_now=a[0]
sum_before=-a[0]
count_1=0
count_2=0
for i in range(n):
    while sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=-a[1]/abs(a[1])
            count_1+=1
        else:
            count_1+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]

sum_now=a[0]
sum_before=-a[0]
if sum_before==0:
    sum_now=a[1]/abs(a[1])
    sum_before=-sum_now
    count_2+=1
else:
    count_2+=abs(int(sum_now))+1
    sum_now=-sum_now/abs(sum_now)
    sum_before=-sum_now
for i in range(n):
    while sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=a[1]/abs(a[1])
            count_2+=1
        else:
            count_2+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]
print(min(count_1, count_2))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
sum_now=a[0]
sum_before=-a[0]
count_1=0
count_2=0
for i in range(n):
    if sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=-a[1]/abs(a[1])
            count_1+=1
        else:
            count_1+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]

sum_now=a[0]
sum_before=-a[0]
if sum_before==0:
    sum_now=a[1]/abs(a[1])
    sum_before=-sum_now
    count_2+=1
else:
    count_2+=abs(int(sum_now))+1
    sum_now=-sum_now/abs(sum_now)
    sum_before=-sum_now
for i in range(n):
    if sum_now*sum_before>=0:
        if sum_before==0:
            sum_now=a[1]/abs(a[1])
            count_2+=1
        else:
            count_2+=abs(int(sum_now))+1
            sum_now=-sum_before/abs(sum_before)
    if i!=n-1:
        sum_before=sum_now
        sum_now=sum_now+a[i+1]
print(min(count_1, count_2))
### BUGGY CODE ###

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

for i in range(n):
    ans.append(1+a.index(i+1))
print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(n)]

for i in range(n):
    ans[a[i]-1] = i+1
print(*ans)
### BUGGY CODE ###

N = int(input())
A = list(int(x) for x in input().split())
a = len(A)
sa = sorted(A)
su = 0
for i in range(a):
        su += sa[i]*sum(sa[i+1:])

print(su%(10**9+7))

### FIXED CODE ###

N = int(input())
A = list(int(x) for x in input().split())
B = [0]
a = len(A)
sa = sorted(A)
su = 0
p = 10**9+7

for i in range(a):
    B.append(B[i] + sa[i])

for j in range(a):
    su += sa[j]*B[j]

print(su%p)
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()

x=[xh[i][0] for i in range(n)]
lst=[]
for i in range(n):
    lst.append([i,bisect.bisect(x,x[i]+2*d)])
# print(lst)

ans=0
for i in range(n):
    if xh[i][1]>0:
        cnt=math.ceil(xh[i][1]/a)
        ans+=cnt
        for j in range(lst[i][0],lst[i][1]):
            xh[j][1]-=cnt*a
        # print(cnt,ans)
        # print(xh)
print(ans)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
r,tama=[],[0]

for i in range(n):
    x,h=xh[i]
    tmpr=bisect.bisect_left(r,x)
    h-=(tama[-1]-tama[tmpr])*a
    tmp=0
    if h>0:
        tmp=math.ceil(h/a)
    tama.append(tmp)
    tama[i+1]+=tama[i]
    r.append(x+2*d)

print(tama[-1])
# print(r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
seen=[False for _ in range(n+1)]

for _ in range(n-1):
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x
    
def dfs(v):
    seen[v]=True
    for nv in Graph[v]:
        if seen[nv]:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv)

dfs(1)
print(*ans[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#普通にinputするよりstdin.readlineのほうがはやい
input = sys.stdin.readline 
n,q=map(int,input().split())
Graph=[[] for _ in range(n+1)]
ans=[0 for _ in range(n+1)]


for _ in range(n-1):
    a,b=map(int,input().split())
    Graph[a].append(b)
    Graph[b].append(a)

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

def dfs(v,par):
    for nv in Graph[v]:
        if nv==par:
            continue
        else:
            ans[nv]+=ans[v]
            dfs(nv,v)

dfs(1,-1)
print(*ans[1:])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
d = N // 2
ans = []
def linking_up():
    for i in range(N):
        if i % 2 == 0 and i != 0:
            if A.count(i) == 2 and A.count(0) == 1:
                ans.append('c')
        else:
            if A.count(i) == 2:
                ans.append('a')
linking_up()
if ans.count('a') == d or ans.count('c')== d:
    print(2 ** d)
else:
    print(0)
        




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
if n%2==0:
  for i in range(n):
    if a[i]!=(i//2)*2+1:
      print(0)
      exit()
  print(pow(2,n//2,mod))
else:
  for i in range(n):
    if a[i]!=((i+1)//2)*2:
      print(0)
      exit()
  print(pow(2,n//2,mod))