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

n = int(input())

def j(b):
    print(b)
    return b, input()[0]

def q(l, r, t):
    m, rm = j((l + r + 1) // 2)
    if (m - b)%2 == (rm != t):
        q(m, r, rm)
    else:
        q(l, m-1, t)

_, s = j(0)
q(0, n-1, s)

### FIXED CODE ###

n = int(input())
q = lambda i:input('%d\n'%i)
i, j = 0, n - 1
a, b = q(i), q(j)
while True:
  k = (j - i + 1) // 2 + i
  c = q(k)
  if (k - i)%2 == (a==c):
    j = k
  else:
    a = c
    i = k
### BUGGY CODE ###

N = int(input())


print(sum(range(N)))

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
    ans = (N+1)*(N//2)
    ans -= N
    print(ans)
else:
    x = (N+1)//2
    ans = x + x * ((N-1)//2) * 2
    ans -= N
    print(ans)
### BUGGY CODE ###

#e
H,W,M = map(int,input().split())
h = [None]*M
w = [None]*M

for i in range(M):
    a,b = map(int,input().split())
    h[i],w[i] = a-1,b-1

exist = [[False]*W for _ in range(H)]
for i in range(M):
    exist[h[i]][w[i]]=True

from collections import Counter
ch = Counter(h)
cw = Counter(w)

print( max(ch[x]+cw[y]-exist[x][y] for x in range(H) for y in range(W) ))

### FIXED CODE ###

#e
H,W,M = map(int,input().split())
h = [None]*M
w = [None]*M
for i in range(M):
    a,b = map(int,input().split())
    h[i],w[i] = a-1,b-1


from collections import Counter
ch = Counter(h)
cw = Counter(w)

x_max=max(ch.values())
cand_x_max = [x for x in range(H) if ch[x]==x_max]

y_max=max(cw.values())
cand_y_max = [y for y in range(W) if cw[y]==y_max]

    
cnt=0
for i in range(M):
    if ch[h[i]]==x_max and cw[w[i]]==y_max:
        cnt+=1
if cnt<len(cand_x_max)*len(cand_y_max):
    print(x_max+y_max)
else:
    print(x_max+y_max-1)
### BUGGY CODE ###

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
  for w in range(W+1):
    if w >= items[i][0]:
      dp[i+1][w] = max(dp[i][w-items[i][0]]+items[i][1], dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]
print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
  for w in range(W+1):
    if w >= items[i][0]:
      dp[i+1][w] = max(dp[i][w-items[i][0]]+items[i][1], dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

N = int(input())
Ai = list(map(int, input().split()))
Distinct = 0
for x in range(N-1):
    if Ai[x] in Ai[x+1:]:
        Distinct += 1

if Distinct == 0:
    print('YES')

else:
    print('NO')

### FIXED CODE ###

N = int(input())
Ai = list(map(int, input().split()))
Ai_set = set(Ai)
if len(Ai) - len(Ai_set) == 0:
    print('YES')

else:
    print('NO')
### BUGGY CODE ###

from sys import stdin
import sys

A, B, N = [int(x) for x in stdin.readline().rstrip().split()]
# N, M = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
ans = 0
for i in range(1, N+1):
    temp = int((A*i)/B)-A*int(i/B)
    if temp > ans:
        # print(i)
        ans = temp
print(ans)


### FIXED CODE ###

from sys import stdin
import sys

A, B, N = [int(x) for x in stdin.readline().rstrip().split()]
# N, M = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
x=min(B-1,N)
ans = int((A*x)/B)-A*int(x/B)
print(ans)
# if N >= B:
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n = int(input())
    al = [int(i) for i in input().split()]
    a = n // 2
    s = sum(al)
    ans = [0] * n
    for i in range(n):
        f = s
        for j in range(a):
            f -= 2 * al[(i - (1 + 2 * (j + 1)) + n) % n]
        ans[i] = f
    ans = ans[1:] + [ans[0]]
    print(" ".join([str(i) for i in ans]))

if __name__=="__main__":
    solve()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n = int(input())
    al = [int(i) for i in input().split()]
    a = n // 2
    s = sum(al)
    ans = [0] * n
    for j in range(a):
        s -= 2 * al[(0 - (1 + 2 * (j + 1)) + n) % n]
    ans[n - 1] = s
    for i in range(n - 2, -1, -1):
        ans[i] = 2 * al[i] - ans[i + 1]
    print(" ".join([str(i) for i in ans]))

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

n, x, y = map(int, input().split())
ans = [0]*n
x, y = min(x, y), max(x, y)

for i in range(1, n):
    for j in range(i+1, n+1):
        # calculate dist(i, j)
        dist = j - i
        dist = min(dist, abs(j - y) + abs(x - i) + 1)
        dist = min(dist, abs(j - x) + abs(y - i) + 1)
        ans[dist] += 1
print("\n".join(list(map(str, ans[1:]))))


### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0]*n
x, y = min(x, y), max(x, y)
 
for i in range(1, n):
    for j in range(i+1, n+1):
        # calculate dist(i, j)
        dist = j - i
        dist = min(dist, abs(j - y) + abs(x - i) + 1)
        dist = min(dist, abs(j - x) + abs(y - i) + 1)
        ans[dist] += 1
print("\n".join(list(map(str, ans[1:]))))
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = [[0]*10 for _ in range(n)]
ans = 0
for i in range(n):
    str_s = input()
    for j in range(10):
        s[i][j] = str_s[j]

for i in range(n):
    s[i].sort()
    s[i] = tuple(s[i])
set_s = set(s)


for item in set_s:
    count = 0
    for j in range(n):
        if item == s[j]:
            count += 1
    ans += count*(count-1)//2
print(ans)




### FIXED CODE ###

from collections import Counter
n = int(input())
s = [[0]*10 for _ in range(n)]
ans = 0
for i in range(n):
    str_s = input()
    for j in range(10):
        s[i][j] = str_s[j]

dict_s = {}
for i in range(n):
    s[i].sort()
    si = "".join(s[i])
    dict_s.setdefault(si, 0)
    dict_s[si] += 1

for x in dict_s.values():
    ans += x*(x-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
idx = [0]
for n in range(1, N+1):
    try:
        idx.append(A[idx[-1]:].index(n) + len(A[:idx[-1]]))
    except:
        break
idx.append(N-1)
if len(idx) == 2:
    print(-1)
else:
    a = [i-j for i,j in zip(idx[1:], idx[:-1])]
    print(sum(a)-(len(idx)-2)+1)

### FIXED CODE ###

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

i = 1
ans = 0
for n in range(N):
  if i == A[n]:
    i += 1
  else:
    ans += 1
if ans == N:
  ans = -1
  
print(ans)
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,Y = map(int,input().split())

    d = [ [ 0 for j in range(N) ] for i in range(N) ]
    d = np.array(d)

    for i in range(1,N):
        for j in range(i,N+1):
            temp1 = abs(j-i)
            temp2 = abs(X-i) + 1 + abs(j-Y)
            temp3 = abs(Y-i) + 1 + abs(j-X)
            d[i-1,j-1] = min(temp1,temp2,temp3)

    for k in range(1,N):
        res = np.count_nonzero(d == k)
        print(res)



main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,Y = map(int,input().split())

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

    for i in range(1,N):
        for j in range(i,N+1):
            temp1 = abs(j-i)
            temp2 = abs(X-i) + 1 + abs(j-Y)
            temp3 = abs(Y-i) + 1 + abs(j-X)
            temp = min(temp1,temp2,temp3)
            cost[temp] += 1

    for k in range(1,N):
        print(cost[k])



main()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

# a = [x//2 for x in a]
# if a[0] % 2 == 0:  # 偶数の時
# 	for x in a:
# 		if x % 2 == 1:
# 			print(0)
# 			sys.exit(0)
# 	for x in a:
# 		if a[0] != x and abs(a[0]-x)%gcd(2*a[0], 2*x) != 0:
# 			print(0)
# 			sys.exit()

# 	tmp = 1
# 	for x in a:
# 		tmp = x*tmp//gcd(x, tmp)
# 	print((M-tmp)//(tmp*2)+1)

# else:
# 	for x in a:
# 		if x % 2 == 0:
# 			print(0)
# 			sys.exit(0)
# 	tmp = 1
# 	for x in a:  # 奇数の時
# 		tmp = x*tmp//gcd(x, tmp)
# 	print((M-tmp)//(tmp*2)+1)

for i in range(1, N):
	if abs(a[0]//2-a[i]//2) % gcd(a[0], a[i]) != 0:
		print(0)
		sys.exit()
tmp = 1
for x in a:
	tmp = x*tmp//gcd(x, tmp)
tmp = tmp//2
print((M-tmp)//(tmp*2)+1)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a = LIST()

a = [x//2 for x in a]
if a[0] % 2 == 0:  # 偶数の時
	for x in a:
		if x % 2 == 1:
			print(0)
			sys.exit(0)
	for x in a:
		if a[0] != x and abs(a[0]-x)%gcd(2*a[0], 2*x) != 0:
			print(0)
			sys.exit()

	tmp = 1
	for x in a:
		tmp = x*tmp//gcd(x, tmp)
	print((M-tmp)//(tmp*2)+1)


else:
	for x in a:
		if x % 2 == 0:
			print(0)
			sys.exit(0)
	tmp = 1
	for x in a:  # 奇数の時
		tmp = x*tmp//gcd(x, tmp)
	print((M-tmp)//(tmp*2)+1)
### BUGGY CODE ###

n, m = map(int, input().split())
s = list(sorted(map(int, input().split())))

for i in range(m):
  num = max(s)
  s.pop(-1)
  s.append(num//2)
  s.sort()
print(sum(s))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
s = list(map(lambda x: x* (-1), map(int, input().split())))

heapq.heapify(s)

while m != 0:
  num = heapq.heappop(s)
  heapq.heappush(s, -1*num//2*-1)
  m -= 1

print(-1 * sum(s))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
for _ in range(N):
  m = max(d.keys())
  x = d[m]
  if rest < x:
    res += rest*m
    break
  else:
    res += x*m
    rest -= x
    del d[m]
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M=(int(x) for x in input().rstrip('\n').split())
As = [int(x) for x in input().rstrip('\n').split()]
d = {}
for x in As:
  if x in d:
    d[x] += 1
  else:
    d[x] = 1
for _ in range(M):
  B,C = (int(x) for x in input().rstrip('\n').split())
  if C in d:
    d[C] += B
  else:
    d[C] = B
res = 0
rest = N
d2 = sorted([x for x in d.keys()],reverse=True)
for m in d2:
  x = d[m]
  if rest < x:
    res += rest*m
    break
  else:
    res += x*m
    rest -= x
print(res)
### BUGGY CODE ###

def 解():
    N,K = [int(_) for _ in input().split()]
    aH = [int(_) for _ in input().split()]
    INF=float("inf")
    dp=[INF]*N
    dp[0]=0
    for i in range(N):
        dp[i] = min(dp[i-j] + abs(aH[i-j]-aH[i]) for j  in  range(min(K+1,i+1)))
    print(dp[-1])
解()


### FIXED CODE ###

def 解():
    N,K = [int(_) for _ in input().split()]
    aH = [int(_) for _ in input().split()]
    INF=float("inf")
    dp=[INF]*N
    dp[0]=0
    for i in range(N):
        dp[i] = min(dp[i-j] + abs(aH[i-j]-aH[i]) for j  in  range(min(K+1,i+1)))
    print(dp[-1])
解()
### BUGGY CODE ###

import copy
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
flag = False

while flag == False:
    #print(moji)
    moji_old = copy.deepcopy(moji)
    for i in range(h*w):
        y = i//w
        x = i%w
        if moji_old[y][x] == '.':
            flag = False
            break
        else:
            flag = True
    
    for i in range(h*w):
        y = i//w
        x = i%w
        #print(i)
        if moji_old[y][x] == '#':
            for j in range(4):
                nx = x+vx[j]
                ny = y+vy[j]
                #print(ny,nx)
                if nx < 0 or nx >= w or ny < 0 or ny >= h:
                    continue
                if moji[ny][nx] == ".":
                    continue
                moji[ny][nx] = '#'
    
    if flag == True:
        break
                
    ans += 1
    
print(ans)

### FIXED CODE ###

import queue
from collections import deque
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

dist = [[-1]*w for _ in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
q = deque()

for i in range(h*w):
    y = i//w
    x = i%w
    #print(i)
    if moji[y][x] == '#':
        q.append(i)
        dist[y][x] = 0

#ans = -1

ans = 0

while q:
    #print(q.qsize())
    tmp = q.popleft()
    y = tmp//w
    x = tmp%w
    d = dist[y][x]
    #print(tmp,num)
    for j in range(4):
        nx = x+vx[j]
        ny = y+vy[j]
        #print(ny,nx)
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue
        if dist[ny][nx] == -1:
            dist[ny][nx] = d+1
            #moji[ny][nx] = '#'
            q.append(ny*w+nx)
    #ans += 1
    ans = max(d,ans)

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

from collections import defaultdict
from queue import PriorityQueue

def dijkstra(G, s):
    q = PriorityQueue()
    prev = [None] * len(G.keys())
    dist = [float('inf')] * len(G.keys())
    dist[s] = 0
    for v in sorted(G.keys()):
        q.put((dist[v],v))
    while not q.empty():
        _, u = q.get()
        for v, d in G[u]:
            tmp = dist[u] + d
            if dist[v] > tmp:
                dist[v] = tmp
                prev[v] = u
                q.put((tmp, v))
    return dist

n, m, s, t = map(int, input().split())
G1 = defaultdict(list)
G2 = defaultdict(list)

for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G1[u].append((v, a))
    G1[v].append((u, a))
    G2[u].append((v, b))
    G2[v].append((u, b))

dist1 = dijkstra(G1, s-1)
dist2 = dijkstra(G2, t-1)

mv = 0
ans = []
for i in range(n-1, -1, -1):
    mv = max(mv, 10**15 - dist1[i] - dist2[i])
    ans.append(mv)

ans.reverse()
for a in ans:
    print(a)

### FIXED CODE ###

from collections import defaultdict
import heapq

def dijkstra(G, s):
    q = []
    heapq.heapify(q)
    prev = [None] * len(G.keys())
    dist = [float('inf')] * len(G.keys())
    dist[s] = 0
    for v in sorted(G.keys()):
        heapq.heappush(q, (dist[v],v))
    while True:
        try:
            _, u = heapq.heappop(q)
        except:
            break
        for v, d in G[u]:
            tmp = dist[u] + d
            if dist[v] > tmp:
                dist[v] = tmp
                prev[v] = u
                heapq.heappush(q, (tmp, v))
    return dist

n, m, s, t = map(int, input().split())
G1 = defaultdict(list)
G2 = defaultdict(list)

for i in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    G1[u].append((v, a))
    G1[v].append((u, a))
    G2[u].append((v, b))
    G2[v].append((u, b))

dist1 = dijkstra(G1, s-1)
dist2 = dijkstra(G2, t-1)

mv = 0
ans = []
for i in range(n-1, -1, -1):
    mv = max(mv, 10**15 - dist1[i] - dist2[i])
    ans.append(mv)

ans.reverse()
for a in ans:
    print(a)
### BUGGY CODE ###

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

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

amax = M // N
L = make_divisor_list(M)
L = [i for i in L if i <= amax]

ans = L[-1]

print(ans)


### FIXED CODE ###

import math

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

# N = 100000
# M = 1000000000

def pfac(n):
    values = [1, n]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            values.append(i)
            values.append(n // i)
    return values

L = pfac(M)
L = [i for i in L if i * N <= M]

ans = []

for i in L[::-1]:
    # if (M - (N * i)) % i == 0:
    if M % i == 0:
        ans.append(i)

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

n=int(input())
a=[input() for _ in range(n)]
a.sort()
b=[]
c=[]
w=""
for m in a:
  if m == w:
    c[-1]+=1
  else:
    b.append(m)
    c.append(1)
    w=m
for m in range(len(b)):
  if c[m]==max(c):
    print (b[m])

### FIXED CODE ###

n=int(input())
a={}
for _ in range(n):
  m=input()
  if m in a:
    a[m]+=1
  else:
    a[m]=1
b=[]
v=max(a.values())
for k in a.items() :
     if k[1] == v:
      b.append(k[0])
b.sort()
for l in b:
  print(l)
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    a1 = [A[0]]
    tmp = A[0]
    for i in range(1, N):
        tmp = tmp ^ A[i]
        a1.append(tmp)
    a2 = list(accumulate(A))
    count = 0
    for l in range(N):
        for r in range(l, N):
            s1 = a1[r] ^ (0 if l == 0 else a1[l - 1])
            s2 = a2[r] - (0 if l == 0 else a2[l - 1])
            if (s1 == s2):
                count += 1
    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
from itertools import accumulate


def main():
    N = int(stdin.readline().rstrip())
    A = [int(x) for x in stdin.readline().rstrip().split()]
    A1 = [A[0]]
    for i in range(1, N):
        A1.append(A1[-1] ^ A[i])
    A2 = list(accumulate(A))
    l = 0
    r = 1
    tmp1 = A1[0]
    tmp2 = A2[0]
    count = 0
    while True:
        if (l == N - 1) and (r == N):
            count += 1
            break

        if (r != N) and (tmp1 ^ A[r + 1 - 1] == tmp2 + A[r + 1 - 1]):
            if tmp1 == tmp2:
                count += 1
            r += 1
            tmp1 = tmp1 ^ A[r - 1]
            tmp2 = tmp2 + A[r - 1]
            continue
        else:
            if tmp1 == tmp2:
                count += (r - l - 1)
            tmp1 = tmp1 ^ A[l]
            tmp2 = tmp2 - A[l]
            l += 1

    print(count)


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

# https://atcoder.jp/contests/abc059/tasks/arc072_a
# C - Sequence
import copy
N = int(input().split()[0])
a_list = list(map(int, input().split()))

w_list_1 = copy.copy(a_list)
w_list_2 = copy.copy(a_list)
c_1, c_2 = 0, 0
c_list = []

for i in range(N):  # 10 ** 5
    # 偶数項を正にする場合
    s_1 = sum(w_list_1[:i+1])

    if i % 2 == 0 and s_1 < 0:
        w_list_1[i] += abs(s_1)
        c_1 += abs(s_1)
    elif i % 2 != 0 and s_1 >= 0:
        w_list_1[i] -= abs(s_1+1)
        c_1 += abs(s_1+1)

    s_1 = sum(w_list_1[:i+1])

    if s_1 == 0:
        a = w_list_1[i]
        w_list_1[i] = a + 1 if a >= 0 else a - 1
        c_1 += 1

    # 偶数項を負にする場合
    s_2 = sum(w_list_2[:i+1])

    if i % 2 == 1 and s_2 < 0:
        w_list_2[i] += abs(s_2)
        c_2 += abs(s_2)
    elif i % 2 != 1 and s_2 >= 0:
        w_list_2[i] -= abs(s_2+1)
        c_2 += abs(s_2+1)

    s_2 = sum(w_list_2[:i+1])

    if s_2 == 0:
        a = w_list_2[i]
        w_list_2[i] = a + 1 if a >= 0 else a - 1
        c_2 += 1

ans = min([c_1, c_2])
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc059/tasks/arc072_a
# C - Sequence
import copy
N = int(input().split()[0])
a_list = list(map(int, input().split()))

w_list_1 = copy.copy(a_list)
w_list_2 = copy.copy(a_list)
c_1, c_2 = 0, 0
s_1, s_2 = 0, 0
c_list = []

for i in range(N):  # 10 ** 5
    # 偶数項を正にする場合
    before = w_list_1[i]
    s_1 += before

    if i % 2 == 0 and s_1 < 0:
        w_list_1[i] += abs(s_1)
        c_1 += abs(s_1)
    elif i % 2 != 0 and s_1 >= 0:
        w_list_1[i] -= abs(s_1+1)
        c_1 += abs(s_1+1)

    s_1 = s_1 - before + w_list_1[i]

    if s_1 == 0:
        a = w_list_1[i]
        w_list_1[i] = a + 1 if a >= 0 else a - 1
        s_1 = 1 if a >= 0 else -1
        c_1 += 1

    # 偶数項を負にする場合
    before = w_list_2[i]
    s_2 += before

    if i % 2 == 1 and s_2 < 0:
        w_list_2[i] += abs(s_2)
        c_2 += abs(s_2)
    elif i % 2 != 1 and s_2 >= 0:
        w_list_2[i] -= abs(s_2+1)
        c_2 += abs(s_2+1)

    s_2 = s_2 - before + w_list_2[i]

    if s_2 == 0:
        a = w_list_2[i]
        w_list_2[i] = a + 1 if a >= 0 else a - 1
        s_2 = 1 if a >= 0 else -1
        c_2 += 1

ans = min([c_1, c_2])
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

L = str(input())
L_list = [0 for i in range(len(L))]
for i in range(len(L)):
    L_list[i] = int(L[i])
n = len(L)
num = 0
L_list.reverse()
for i in range(n):
    num += L_list[i]*2**i


def count2digit(num):
    cnt = 0
    while num > 0:
        if num % 2 == 1:
            cnt +=1
        num //= 2
    return cnt


ans = 3**(n-1) % mod
for i in range(2**(n-1),num+1):
    ans += 2**count2digit(i) % mod
    ans = ans % mod

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

L = str(input())
n = len(L)
dp = [[0,0] for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if L[i] == "0": #a+b = 0
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
    else:
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod

    if L[i] == "0":
        dp[i+1][1] = (dp[i+1][1] + dp[i][1]*2) % mod
    else:
        dp[i+1][0] = (dp[i+1][0] + dp[i][0]*2) % mod
        dp[i+1][1] = (dp[i+1][1] + dp[i][1]*2) % mod


print(sum(dp[n]) % mod)
### BUGGY CODE ###

def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    move = 2 * n
    for i in range(n):
        position = i
        for j in range(move):
            if s[position] == "R":
                position += 1
            else:
                position -= 1
        ans[position] += 1
    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    for i in range(n):
        if s[i] == "R":
            if i != (n - 1) and s[i + 1] == "L":
                ans[i] += 1
                for j in range(i - 2, -1, -2):
                    if s[j] == "R" and s[j + 1] == "R":
                        ans[i] += 1
                    else:
                        break
            for j in range(i + 2, n, 2):
                if s[j - 1] == "L" and s[j] == "L":
                    ans[i] += 1
                else:
                    break
        else:  # s[i] == "L"
            if i != 0 and s[i - 1] == "R":
                ans[i] += 1
                for j in range(i + 2, n, 2):
                    if s[j - 1] == "L" and s[j] == "L":
                        ans[i] += 1
                    else:
                        break
            for j in range(i - 2, -1, -2):
                if s[j] == "R" and s[j + 1] == "R":
                    ans[i] += 1
                else:
                    break
    print(*ans)


if __name__ == '__main__':
    main()