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

import sys
sys.setrecursionlimit(10 ** 7)

def solve(G, p, ans, st, fst):
    cnt_1 = 0
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            return False
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst):
            return True
        st.remove(nxt)
    return False

def main():
    n, m = map(int, input().split())
    G = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].add(b)
    ans = []
    f = False
    st = set()
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def solve(G, p, ans, st, fst, arr, x):
    arr[p] = x
    cnt_1 = 0
    z = -1
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
            z = nxt
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            k = arr[z]
            for v in st:
                if arr[v] >= k:
                    ans.append(v)
            return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst, arr, x+1):
            return True
        st.remove(nxt)
    arr[p] = 0
    return False

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
    ans = []
    f = False
    st = set()
    arr = [0]*(n+1)
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i, arr, 1):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

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

from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    L = 0
    R = 0
    
    agg = [[0]*(w) for _ in range(cnt+1)]
    prev = 0
    for i in range(w):
        c = 0
        for j, split in enumerate(map(int, x+('1',))):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False
    for xyz in zip(*agg):
        if any(x > k for x in xyz):
            cannot_split = True
            break

        if all(x+tmp[i] <= k for i, x in enumerate(xyz)):
            for i, x in enumerate(xyz):
                tmp[i] += x
            continue
        for i, x in enumerate(xyz):
            tmp[i] = x
        cnt += 1

    if cannot_split:
        continue
        
    ans = min(ans, cnt)
print(ans)


### FIXED CODE ###

from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False

    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

n = int(input())
L = [int(i) for i in input().split()]

L.sort()

ans = 0
for a in range(len(L)):
    for b in range(a+1,len(L)):
        c_max = L[a]+L[b]-1
        left = b+1
        right = len(L)
        mid = (right+left)//2
        while left<right:
            mid = (right+left)//2
            if c_max < L[mid]:
                right = mid
            else:
                left = mid+1
        ans += left-(b+1)
       
        
        
print(ans)

### FIXED CODE ###

import bisect
import copy

#bisect2回使用する計算はアウト

N = int(input())
L = [int(i) for i in input().split()]
L.sort()
ans = 0
for i in range(N):
    for j in range(i+1,N):
        Max = bisect.bisect_left(L,L[i]+L[j])
        ans += max(Max-(j+1),0)
print(ans)
### BUGGY CODE ###

def mm(k,s1,s2,s3):
	if(len(k) == 1):
		if(s1 == k[0] or s2 == k[0] or s3 == k[0]):
			return 1
		else:
			return 0
	else:
		t = 0
		if(k[0] <= s1):
			t += mm(k[1:],s1-k[0],s2,s3)
		if(k[0] <= s2):
			t += mm(k[1:],s1,s2-k[0],s3)
		if(k[0] <= s3):
			t += mm(k[1:],s1,s2,s3-k[0])
		return t

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort(reverse=True)
count = 0
suma = sum(a)
for i in range(suma-suma*2/3,suma-(suma/2)):
	for j in range(suma-i-(suma-i)/2,i+1):
		temp = mm(a,i,j,suma-i-j)
		if(i == j or j == suma-i-j):
			if(i == suma-i-j):
				count += temp
			else:
				count += temp*3
		else:
			count += temp*6
print(count)

### FIXED CODE ###

import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2),dtype = np.int)
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
	if(i%10 == 0):
		dp[i,:,:] = dp[i,:,:]%DIV
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))
### BUGGY CODE ###

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

while True:
    delta = abs(N - K)
    if delta <N:
        N = delta

    else:
        print(N)
        break



### FIXED CODE ###

N, K = map(int, input().split())
if N % K == 0:
    print(0)

else:
    num = N//K
    delta = abs(N-num*K)
    if delta > abs(delta-K):
        print(abs(delta-K))
    else:
        print(delta)
### BUGGY CODE ###



if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    constructions=[list(map(int,input().split())) for i in range(N)]
    D=[int(input()) for i in range(Q)]
    ans={i:-1 for i in range(Q)}
    constructions.sort(key=lambda x:x[2])

    for i,p in enumerate(D):
        for construction in constructions:
            S=construction[0]
            T=construction[1]
            X=construction[2]
            if S<=X+p<T:
                ans[i]=X
                break
    for i in ans.values():
        print(i)


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


n, q = map(int, input().split())
events = [list(map(int, input().split())) for _ in range(n)]
events.sort(key=lambda x: x[2])

departures = [int(input()) for _ in range(q)]


ans = ['-1'] * q
skip = [-1] * q

for start, end, pos in events:
    left = bisect.bisect_left(departures, start-pos)
    right = bisect.bisect_left(departures, end-pos)

    while left < right:
        if skip[left] == -1:
            ans[left] = str(pos)
            skip[left] = right
            left += 1

        else:
            left = skip[left]

print('\n'.join(ans))
### BUGGY CODE ###

n=int(input())

x=[-1]*(n+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=n:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>n or j>x[i]:break
        x[j*i]=j
    i+=1

def f(k):
    z=[]
    if k==1:
        return 1
    p=x[k]
    c=1
    while k>1:
        if p!=x[k//p]:
            z.append(c)
            c=1
        else:
            c+=1

        k=k//p
        p=x[k]

    ans=1
    for i in range(len(z)):
        ans=ans*(z[i]+1)
    return ans
s=0
for i in range(n):
    s+=(i+1)*f(i+1)
print(s)



### FIXED CODE ###

n=int(input())
x=[-1]*(10**7+5)
x[0]=0
x[1]=1
i=2
while i<=10**7+1:
    j=2*i
    if x[i]==-1:
        x[i]=i
        while j<=10**7+1:
            if x[j]==-1:x[j]=i
            j+=i
    i+=1
def f(k):
    if k==1:
        return 1

    z=[]
    p=x[k]
    m=1
    ans=1
    while k>=2:
        k=k//p
        if p==x[k]:
            m+=1
        else:
            z.append(m)
            m=1
            p=x[k]

    for i in range(len(z)):
        ans*=z[i]+1
    return ans
s=0
for i in range(1,n+1):
    s+=i*f(i)
print(s)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
ans = 0
for i in range(1,n):
    ai = a[i:] + a[:-i]
    ans += np.count_nonzero(ai==i)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a1,a2 = [],[]
for i in range(n):
    a1.append(i+a[i])
    a2.append(i-a[i])
a1,a2 = Counter(a1),Counter(a2)
rng = max(a2)
ans = 0
for i in range(1,rng+1):
    if i in a1 and i in a2:
        ans += a1[i]*a2[i]
print(ans)
### BUGGY CODE ###

n = input()
n = int(n)

li = [int(input()) for i in range(n)]
m = max(li)
for j in range(n):
  buf = li.pop(j)
  if buf<m:
    print(m)
  else:
  	print(max(li))
  li.insert(j,buf)


### FIXED CODE ###

n = input()
n = int(n)

li = [int(input()) for i in range(n)]
m = max(li)
m2 = sorted(li)[-2]

for j in range(n):
  if m == li[j]:
    print(m2)
  else:
    print(m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    for _ in range(q):
        l, r = MI1()
        s = S[l:r+1]
        # print(s, s.count('AC'))
        print(s.count('AC'))

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, q = MI()
    S = input()
    ats = [0]
    cnt = 0
    for i in range(n-1):
        j = i + 2
        s = S[i:j]
        # print(s)
        if s == 'AC':
            cnt += 1
        ats.append(cnt)
    # print(ats)
    for _ in range(q):
        l, r = MI1()
        # print(S[l:r+1])
        print(ats[r] - ats[l])


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

import numpy as np
N, K = map(int,input().split())
td = np.empty((N,2),dtype=np.int64)
for i in range(N):
    td[i] = list(map(int,input().split()))

t = td[:,0]-1
d = td[:,1]
order1=np.argsort(d)[::-1]
mins = len(set(t[order1[:K]]))

best = -np.ones(N,dtype=np.int64)
for i in range(N):
    if best[t[i]] < 0 or d[i] > d[best[t[i]]]:
        best[t[i]]=i

bestmenu = np.array(list(set(best) - set([-1])),dtype=np.int64)
othermenu = np.array(list(set(range(N)) - set(bestmenu)),dtype=np.int64)

maxs = min(len(bestmenu),K)
ans = 0
bests=0
for s in range(mins,maxs+1):
    score = s*s + np.sort(d[bestmenu])[::-1][:s].sum() + np.sort(d[othermenu])[::-1][:(K-s)].sum()
    if score > ans:
        bests=s
        ans = score

print(ans)

### FIXED CODE ###

import numpy as np
N, K = map(int,input().split())
td = np.empty((N,2),dtype=np.int64)
for i in range(N):
    td[i] = list(map(int,input().split()))

t = td[:,0]-1
d = td[:,1]
order1=np.argsort(d)[::-1]
mins = len(set(t[order1[:K]]))

best = -np.ones(N,dtype=np.int64)
for i in range(N):
    if best[t[i]] < 0 or d[i] > d[best[t[i]]]:
        best[t[i]]=i

bestmenu = np.array(list(set(best) - set([-1])),dtype=np.int64)
othermenu = np.array(list(set(range(N)) - set(bestmenu)),dtype=np.int64)

maxs = min(len(bestmenu),K)
ans = 0
bests=0
sorted_d_best=np.sort(d[bestmenu])[::-1]
sorted_d_other=np.sort(d[othermenu])[::-1]
for s in range(mins,maxs+1):
    score = s*s + sorted_d_best[:s].sum() + sorted_d_other[:(K-s)].sum()
    if score > ans:
        bests=s
        ans = score

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

N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

ans = 0
#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    if (St[i] == St[j]): 
      dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1)
      ans = max(ans, min(dp[i][j], j-i))
      
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = S[i:i+l]
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]

    dp = [[set() for _ in range(W)] for _ in range(H)]
    dp[0][0] = {A[0][0] - B[0][0], B[0][0] - A[0][0]}
    for h in range(H):
        for w in range(W):
            a, b = A[h][w], B[h][w]
            if w - 1 >= 0:
                for num in dp[h][w - 1]:
                    dp[h][w].add(num + a - b)
                    dp[h][w].add(num + b - a)
            if h - 1 >= 0:
                for num in dp[h - 1][w]:
                    dp[h][w].add(num + a - b)
                    dp[h][w].add(num + b - a)

    res = f_inf
    for num in dp[-1][-1]:
        res = min(res, abs(num))
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]

    dp = [[set() for _ in range(W)] for _ in range(H)]
    dp[0][0] = {abs(A[0][0] - B[0][0])}
    for h in range(H):
        for w in range(W):
            a, b = A[h][w], B[h][w]
            if w - 1 >= 0:
                for num in dp[h][w - 1]:
                    dp[h][w].add(abs(num + a - b))
                    dp[h][w].add(abs(-num + a - b))
            if h - 1 >= 0:
                for num in dp[h - 1][w]:
                    dp[h][w].add(abs(num + a - b))
                    dp[h][w].add(abs(-num + a - b))

    res = f_inf
    for num in dp[-1][-1]:
        res = min(res, abs(num))
    print(res)


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

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()

ans = 0
k = 1
for i in range(60):
    s = 0
    t = 0
    for j in range(n):
        if a[j] % 2 == 0:
            s += 1
        else:
            t += 1
        a[j] //= 2
    ans = ( ans + s * t * k ) % ( 10**9 + 7 )
    k *= 2
print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()

ans = 0
k = 1
for i in range(60):
    s = 0
    t = 0
    for j in range(n):
        if a[j] % 2 == 0:
            s += 1
        else:
            t += 1
        a[j] //= 2
    ans = ( ans + s * t * k ) % ( 10**9 + 7 )
    k *= 2
print(ans)
### BUGGY CODE ###

n = int(input())
def move(max_num,before):
  return min(max_num,before)

people = [n,0,0,0,0,0]
max_nums = []
for i in range(5):
  max_nums.append(int(input()))

time = 0
while True:
  time += 1
  move_p = [0] * 6
  for i in range(5):
    move_p[i] -= min(max_nums[i],people[i])
    move_p[i+1] += min(max_nums[i],people[i])
  people += move_p
  if people[-1] == n:
    break



### FIXED CODE ###

n = int(input())

max_nums = []
for i in range(5):
  max_nums.append(int(input()))
max_nums.append(n)
a = n/min(max_nums)
print(int(a) +4+ (0 if a == int(a) else 1))
### BUGGY CODE ###


from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
l=deque()
l.append(0)
while True:
  flag=True
  for i in path[l[0]]:
    if not i in l:
      l.appendleft(i)
      flag=False
      break
  for i in path[l[-1]]:
    if not i in l:
      l.append(i)
      flag=False
      break
  if flag or len(l)==n:
    break
print(len(l))
for i in range(len(l)):
  l[i]+=1
print(*l)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  path[a-1].append(b-1)
  path[b-1].append(a-1)
l=deque()
s=set()
l.append(0)
s.add(0)
while True:
  for i in path[l[0]]:
    if not i in s:
      l.appendleft(i)
      s.add(i)
      break
  else:break
while True:
  for i in path[l[-1]]:
    if not i in s:
      l.append(i)
      s.add(i)
      break
  else:break
print(len(l))
l=list(map(lambda x:x+1,l))
print(*l)
### BUGGY CODE ###

# Hello World program in Python
def gcd(a,b):
    if not b: return a
    return gcd(b,a%b)
def lcm(a, b):
    return (a*b)//gcd(a, b)
N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007
for x in A:
    l = lcm(l, x)
for x in A:
    ans = (ans + l//x) % mod
print(int(ans))


### FIXED CODE ###

def gcd(a,b):
    if not b: return a
    return gcd(b,a%b)

def lcm(a, b):
    return (a*b)//gcd(a, b)

N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007

for x in A:
    l = lcm(l, x)

for x in A:
    ans = ans + l//x
print(ans % mod)
### BUGGY CODE ###

def sign(x):
    if x>0:
        return 1
    elif x<0:
        return -1
    else:
        return 0


n = int(input())
a = [int(i) for i in input().split()]
s = [sum(a[:i+1]) for i in range(n)]
sp = [s[i] for i in range(n)]
sm = [s[i] for i in range(n)]
P0=0
M0=0
if s[0]==0:
    P0+=1
    M0+=1
    for j in range(n):
        sp[j]+=1
        sm[j]+=1
elif s[0]>0:
    M0+=abs(s[0]+1)
    for j in range(n):
        sm[j]-=(abs(s[0])+1)
else:
    P0+=abs(s[0]+1)
    for j in range(n):
        sp[j]+=(abs(s[0])+1)
for i in range(1,n):
    if sm[i-1]*sm[i]>=0:
        M0+=abs(sm[i])+1
        h=sign(sm[i-1])*(-1)*(abs(sm[i])+1)
        for j in range(i,n):
            sm[j]+=h
    if sp[i-1]*sp[i]>=0:
        P0+=abs(sp[i])+1
        h=sign(sp[i-1])*(-1)*(abs(sp[i])+1)
        for j in range(i,n):
            sp[j]+=h
print(min([M0,P0]))


### FIXED CODE ###

def sign(p):
    if p<0:
        return -1
    elif p>0:
        return 1
    else:
        return 0
N=int(input())
a=[int(i) for i in input().split()]
m=[0,0]
for sgn in [-1,1]:
    x=0
    S=0
    for i in range(N):
        S+=a[i]
        if sign(S)==sgn*(-1)**(i%2) or sign(S)==0:
            x+=abs(S)+1
            S=sgn*(-1)**((i+1)%2)
    m[(sgn+1)//2]=x
print(min(m))
### BUGGY CODE ###

def totalcost_recur(i,cost,N,lookup):
  if i>=N:
    return 0
  if i in lookup:
      return lookup[i]
  option1 = abs(cost[i]-cost[i+1]) + totalcost_recur(i+1,cost,N,lookup)
  ans = option1
  if i+2<=N:
    option2 = abs(cost[i]-cost[i+2]) + totalcost_recur(i+2,cost,N,lookup)
    ans = min(option2,ans)
  lookup[i] = ans
  return ans



def totalcost_dp(cost,N,k):
    dp = [0]*(N+1)
    dp[1] = 0
    
    i = 2
    while i<=N:
        ans = float('inf')
        for j in range(1,k+1):
            if i-j < 1:
                break
            option = dp[i-j]+abs(cost[i]-cost[i-j])
            ans = min(ans,option)
        
        dp[i] = ans
        i+=1

    return dp[N]


n ,k= map(int,input().split())
cost = list(map(int,input().split()))
cost = [0]+cost
lookup = {}

print(totalcost_dp(cost,n,k))

### FIXED CODE ###


def totalcost_dp(cost,N,k):
    dp = [float('inf')]*(N+1)
    dp[1] = 0
    
    
    for i in range(1,N+1):
        
        for j in range(i+1,k+i+1):
            if j < N+1:
                dp[j] = min(dp[j],dp[i]+abs(cost[i]-cost[j]))
                
    return dp[N]


n ,k= map(int,input().split())
cost = list(map(int,input().split()))
cost = [0]+cost
print(totalcost_dp(cost,n,k))
### BUGGY CODE ###

n = int(input())
s = input()

dic = {}
for s_i in s:
	dic[s_i] = s.count(s_i)+1

res = 1
for v in dic.values():
	res = res*v

p = 10**9+7
print((res-1)%p)

### FIXED CODE ###

n = int(input())
s = input()

dic = {}
for s_i in set(s):
	dic[s_i] = s.count(s_i)+1

p = 10**9+7
res = 1
for v in dic.values():
	res = (res*v)%p

print(res-1)
### BUGGY CODE ###

N =int(input())
ans = 0
for j in range(2,N):
  for i in range(N//j,N//(j-1)):
    if (N//i) == N%i:
        ans += i
print(ans)

### FIXED CODE ###

import math
def prime_divisor(n):
    ls = []
    i = 2
    while i <= math.floor(n**0.5):
        if n%i == 0:
            ls.append(i)
            ls.append(n//i)
            i += 1
        else:
            i += 1
    if n > 1:
        ls.append(n)
    return ls
N = int(input())
ls1 = prime_divisor(N)
ls2 = [x-1 for x in list(set(ls1)) if x >= 2]
ls2.sort()
ls2.reverse()
ans = 0
for i in range(len(ls2)):
    if N // ls2[i] == N % ls2[i]:
        ans += ls2[i]
print(ans)