Harryxun/stf_run huggingface dataset:
D - Derangement
def swap(index, swap_with_right):
  global p

  if swap_with_right:
    l = index
    r = index + 1
  else:
    l = index - 1
    r = index

  pl = p[l]
  pr = p[r]
  p[l] = pr
  p[r] = pl


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

p.insert(0, 0)
ans = 0

if p[1] == 1:
  swap(1, True)
  ans += 1

for i in range(2, N+1):
  if i == p[i]:
    if p[i-1] == i:
      swap(i, True)

    ans += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Derangement
def swap(index, swap_with_right):
  global p

  if swap_with_right:
    l = index
    r = index + 1
  else:
    l = index - 1
    r = index

  pl = p[l]
  pr = p[r]
  p[l] = pr
  p[r] = pl


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

p.insert(0, 0)
ans = 0

if p[1] == 1:
  swap(1, True)
  ans += 1

for i in range(2, N+1):
	if i < N:
		if i == p[i] and i+1 == p[i+1]:
			swap(i, True)
			ans += 1
		elif i == p[i]:
			ans += 1
	elif i == p[i]:
		ans += 1

print(ans)
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = shortest_path(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        d = wf[r1-1][r2-1]
        if d == float('inf'):
            break
        cand += int(d)
    if ans < 0 or ans > cand:
        ans = cand

print(ans)


### FIXED CODE ###

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = floyd_warshall(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)
import sys
input = sys.stdin.readline

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

from queue import Queue
q = Queue()
ans = Queue()

import numpy as np
n = np.array(n)


def bfs(b):
    q.put(b)
    ans.put([])

    while q.empty() == False:
        p = q.get()
        a = ans.get()

        if p == []:
            break

        if p[0] != 1:
            continue

        for i, pp in enumerate(p):
            if pp == i+1:
                q.put(p[:i]+p[i+1:])
                ans.put(a+[i+1])


    if p == []:
        a = a[::-1]
        for aa in a:
            print(aa)
    else:
        print(-1)


bfs(b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from queue import Queue
q = Queue()
ans = Queue()

import numpy as np
n = np.array(n)


def bfs(b):
    q.put(b)
    ans.put([])

    while q.empty() == False:
        p = q.get()
        a = ans.get()

        if p == []:
            break

        if p[0] != 1:
            continue

        m = len(p)

        for i in range(m-1, -1, -1):
            if p[i] == i+1:
                q.put(p[:i]+p[i+1:])
                ans.put(a+[i+1])
                break


    if p == []:
        a = a[::-1]
        for aa in a:
            print(aa)
    else:
        print(-1)


bfs(b)
n=int(input())
m=list(map(int,input().split()))
ans=0

for i in range(n+1):
  if m[0] <= m[i]:
    ans += 1
print(ans)

### FIXED CODE ###

n=int(input())
m=list(map(int,input().split()))
ans=1

for i in range(1,n):
  if max(m[:i]) <= m[i]:
    ans += 1
print(ans)
N = int(input())

# 最初の符号
print(0, flush=True)
first = input()

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 1
has = N - 1

while has - notHas > 1:
    print('--{} , {}--'.format(notHas, has))
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid

print(notHas, flush=True)
ret = input()

if ret == 'Vacant':
    exit()

print(has, flush=True)
input()
exit()

### FIXED CODE ###

N = int(input())

# 最初の符号
print(0, flush=True)
first = input()

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 1
has = N - 1

while has - notHas > 1:
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid

print(notHas, flush=True)
ret = input()

if ret == 'Vacant':
    exit()

print(has, flush=True)
input()
exit()
d = input()
a = input().split()
r = 0
for i in a:
    r += 1 / i
print(1 / r)

### FIXED CODE ###

d = input()
a = input().split()
r = 0
for i in a:
    r += 1 / int(i)
print(1 / r)
def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    
    if len(tree_dic) == 0:  #   これなしでいい？
        return ans
    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:
#        if next_node not in tree_dic[current_node]:#   これなしでいい？
#            print("second time")
#            continue    #   深さ優先探索の過程ですでに通ったノードをもう一度通ろうとしたとき
#        else:

        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)
        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
#                print()
            
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)



    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)



### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    next_node_lst = tree_dic[current_node][:]

    for next_node in next_node_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)

        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)
p = list(map(int,input()split()))
if p[0] != p[1] and p[1] != p[2] and p[2] != p[0]:
  print(3)
elif p[0] == p[1] == p[2]:
  print(1)
else:
  print(2)

### FIXED CODE ###

p = list(map(int,input().split()))
if p[0] != p[1] and p[1] != p[2] and p[2] != p[0]:
  print(3)
elif p[0] == p[1] == p[2]:
  print(1)
else:
  print(2)
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)

    N, Q = map(int, input().split())
    G = [set() for _ in range(N)]
    cnt = [0]*N
    visited = [0]*N

    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].add(b)
        G[b].add(a)

    for _ in range(Q):
        node, x = map(int, input().split())
        node -= 1
        cnt[node] += x

    visited[0]=1
    st = [0]
    while st:
        v = st.popleft()
        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = 1
            cnt[u] += cnt[v]
            st.append(u)    

    print(*cnt)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

N, Q = map(int, input().split())
G = [set() for _ in range(N)]
cnt = [0]*N
visited = [0]*N

def dfs(start_node):
    for i in G[start_node]:
        if visited[i]==0:
            visited[i]=1
            cnt[i] += cnt[start_node]
            dfs(i)

for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

for i in range(Q):
    node, x = map(int, input().split())
    node -= 1
    cnt[node] += x

visited[0]=1
#dfs(0)
st = [0]
while st:
    v = st.pop()
    for u in G[v]:
        if visited[u]: continue
        visited[u] = 1
        cnt[u] += cnt[v]
        st.append(u)    

ans = map(str, cnt)
print(' '.join(ans))
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = iil()

l = [0]*9
for i in A:
    l[i//400] += 1

lf = l[:-1]
ans = 8-lf.count(0)
print(ans,ans+l[8])


### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = iil()

l = [0]*9
for i in A:
    l[min(i//400,8)] += 1

lf = l[:-1]
ans = 8-lf.count(0)
print(max(1,ans),ans+l[8])
n = int(input())
a = [1 / int(input()) for _ in range(n)]
print(1 / sum(a))
  

### FIXED CODE ###

n = int(input())
a = [1 / int(x) for x in input().split()]
print(1 / sum(a))
X, Y, R, G, W = map(int, input().split())
red = sorted(list(map(int, input().split())), key=lambda x: -x)
green = sorted(list(map(int, input().split())), key=lambda x: -x)
white = sorted(list(map(int, input().split())), key=lambda x: -x)

dp = [[[0 for _ in range(X+Y+1)] for __ in range(Y+1)] for ___ in range(X+1)]

ans = 0

for w in range(min(W, X+Y)+1):
    for x in range(X+1):
        for y in range(Y+1):
            if x + y + w == X + Y:
                ans = max(ans, dp[x][y][w])
                break
            if x < X:
                dp[x+1][y][w] = max(dp[x+1][y][w], dp[x][y][w] + red[x])
            if y < Y:
                dp[x][y+1][w] = max(dp[x][y+1][w], dp[x][y][w] + green[y])
            if w < W:
                dp[x][y][w+1] = max(dp[x][y][w+1], dp[x][y][w] + white[w])

print(ans)


### FIXED CODE ###

X, Y, R, G, W = map(int, input().split())
red = list(map(lambda x: (int(x), 0), input().split()))
green = list(map(lambda x: (int(x), 1), input().split()))
white = list(map(lambda x: (int(x), 2), input().split()))

apples = sorted(red + green + white, key=lambda x: x[0])

choice = X + Y
res = 0

while apples and choice:
    val, color = apples.pop()
    if color == 0:
        if X > 0:
            res += val
            X -= 1
            choice -= 1
        continue
    if color == 1:
        if Y > 0:
            res += val
            Y -= 1
            choice -= 1
        continue
    if color == 2:
        res += val
        choice -= 1

print(res)
from collections import Counter
H, W, M = map(int, input().split())

h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = map(int, input().split())


S = Counter(h)
T = Counter(w)

if (S.most_common()[0][1] > T.most_common()[0][1]):
    smc = S.most_common()[0][0]
    for i in range(M):
        if (h[i] == smc):
            w[i] = 'boom'

    w1 = [s for s in w if s != 'boom']
    T = Counter(w1)
    tmc = T.most_common()[0][0]
    for i in range(len(w1)):
        if (w1[i] == tmc):
            w1[i] = 'boom' 

    w2 = [s for s in w1 if s != 'boom']
    print(M-len(w2))

else:
    tmc = T.most_common()[0][0]
    for i in range(M):
        if (w[i] == tmc):
            h[i] = 'boom'

    h1 = [s for s in h if s != 'boom']
    S = Counter(h1)
    smc = S.most_common()[0][0]
    for i in range(len(h1)):
        if (h1[i] == S.most_common()[0][0]):
            h1[i] = 'boom' 

    h2 = [s for s in h1 if s != 'boom']
    print(M-len(h2))

### FIXED CODE ###

from collections import Counter
import sys
H, W, M = map(int, input().split())

h = [0] * M
w = [0] * M
for i in range(M):
    h[i], w[i] = map(int, input().split())


S = Counter(h)
T = Counter(w)

if (M == 1):
    print(1)

else:
    if (S.most_common()[0][1] > T.most_common()[0][1]):
        smc = S.most_common()[0][0]
        for i in range(M):
            if (h[i] == smc):
                w[i] = 'boom'

        w1 = [s for s in w if s != 'boom']
        T = Counter(w1)
        if (len(w1) == 0):
            print(M)
            sys.exit()
        tmc = T.most_common()[0][0]
        for i in range(len(w1)):
            if (w1[i] == tmc):
                w1[i] = 'boom' 

        w2 = [s for s in w1 if s != 'boom']
        print(M-len(w2))

    else:
        tmc = T.most_common()[0][0]
        for i in range(M):
            if (w[i] == tmc):
                h[i] = 'boom'

        h1 = [s for s in h if s != 'boom']
        S = Counter(h1)
        if (len(h1) == 0):
            print(M)
            sys.exit()
        smc = S.most_common()[0][0]
        for i in range(len(h1)):
            if (h1[i] == smc):
                h1[i] = 'boom' 

        h2 = [s for s in h1 if s != 'boom']
        print(M-len(h2))
N, K = map(int, input().split())
V = list(map(int, input().split()))

ans = -10**9
R = min(N, K)
A = R
for a in range(0, A+1):
    B = R-a
    for b in range(0, B+1):
        if b>0:
            v = V[:a] + V[-b:]
        else:
            v = V[:a]
        
        v.sort()
        
        cnt = 0
        for vv in v:
            if vv<0:
                cnt += 1
            else:
                break
        ans = max(ans, sum(v[min(K-a-b, cnt):]))
        
print(ans)

### FIXED CODE ###

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

ans = -10**9
R = min(N, K)
A = R
for a in range(0, A+1):
    B = R-a
    for b in range(0, B+1):
        if b>0:
            v = V[:a] + V[-b:]
        else:
            v = V[:a]
        
        v.sort()
        
        cnt = 0
        for vv in v:
            if vv<0:
                cnt += 1
            else:
                break
        ans = max(ans, sum(v[min(K-a-b, cnt):]))
        
print(ans)
n = int(input())
if n % 10 == 3:
  print('bon')
else if n % 10 in [0, 1, 6, 8]:
  print('pon')
else:
  print('hon')

### FIXED CODE ###

n = int(input())
if n % 10 == 3:
  print('bon')
elif n % 10 in [0, 1, 6, 8]:
  print('pon')
else:
  print('hon')
a=input()
print(a[0]+len(a)+a[-1])

### FIXED CODE ###

a=input()
print(a[0]+str(len(a)-2)+a[-1])
m, n = map( int, input().split() )
a = 0
for i in range(m)
	a += int(input())

n=n-a
if a<=-2:
  a=-1

print(a)

### FIXED CODE ###

n, m = map( int, input().split() )
a = list(map(int,input().split()))
sum=0
for i in range(m):
  sum+=a[i]

n=n-sum
if n<=-2:
  n=-1

print(n)
H,W = map(int,input().split())
    print((H*W)//2+(H*W)%2)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H,W = map(int,input().split())
    if H == 1 or W == 1:
        print(1)
    else:
        print((H*W)//2+(H*W)%2)
    
if __name__ == "__main__":
    main()
s = list(str(i) for i input().split())
n = int(input())
k = int(input())

s = s[k]
s = s.lower()
print(s)


### FIXED CODE ###

N, K = (int(i) for i in input().split())
S = list(input())

S[K - 1] = S[K - 1].lower()
print(''.join(S))
import math
 
N = int(input())
 
cnt = 0
 
if N == 2:
  print(1)
  exit()
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return divisors
res1 = sorted(make_divisors(N))
res1 = res1[1:math.ceil(len(res1)/2)]
 
for num in res1:
  kensa = N
  while True:
    if kensa % num == 0:
      kensa = kensa // num
      continue
    break
  if kensa % num == 1:
    cnt += 1
 
res2 = sorted(make_divisors(N-1))
cnt += len(res2[1:])+1
 
print(cnt)

### FIXED CODE ###

X, Y, Z = map(int, input().split())

print(Z, X, Y)
from collections import deque
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
A=list(map(int,input().split()))
queue=deque(A)
for i in range(M):
    queue.append([max(queue)//2])
    queue.remove(max(queue))
print(sum(queue))

### FIXED CODE ###

from heapq import heappop,heappush,heapify
n,m=map(int,input().split())
A=list(map(int,input().split()))
A_m=list(map(lambda x: -x,A))
heapify(A_m)
pop=lambda: -heappop(A_m)
push=lambda x: heappush(A_m,-x)
for _ in range(m):
    x=pop()
    push(x//2)
print(-sum(A_m))
args = input()
if 'A' not in args:
  print('No')
  return
if 'B' not in args:
  print('No')
  return
print('yes')
  


### FIXED CODE ###

args = input()
if 'A' in args:
  if 'B' in args:
    print('Yes')
    exit()
print('No')
A, B, C, D, E, F=map(int, input().split())
a=[]
for i in range(101):
    for j in range(101):
        for k in range(101):
            for l in range(101):
                x=100*A*i+100*B*j
                y=C*k+D*l
                if x+y>F or x==0 or y==0:
                    break
                if 100*y//(x+y)<=(E*100)/(100+E):
                    a.append([str(x+y),str(y)])
print(' '.join(sorted(a, key=lambda x: (100*int(x[1]))/int(x[0]) if int(x[0])!=0 else 0)[-1]))


### FIXED CODE ###

A, B, C, D, E, F=map(int, input().split())
a=[[str(100*A),'0']]
for i in range(101):
    for j in range(101):
        for k in range(101):
            for l in range(101):
                x=100*A*i+100*B*j
                y=C*k+D*l
                if x+y>F or x==0:
                    break
                if 100*y/(x+y)<=(E*100)/(100+E):
                    a.append([str(x+y),str(y)])
print(' '.join(sorted(a, key=lambda x: (100*int(x[1]))/int(x[0]) if int(x[0])!=0 else 0)[-1]))
def inpl():
    return list(map(int, input().split()))


def gcd(a, b):
    # greatest common divisor
    la = max(a, b)
    sm = min(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la - sm)


def lcm(a, b):
    # least common multiple
    return a * b // gcd(a, b)


R, G, B, N = inpl()
ans = 0
for r in range(N // R + 1):
    rest = N - r * R
    x = 0
    while (G * x) % B != rest % B:
        x += 1
    if rest - G * x < 0:
        continue
    ans += (rest - G * x) // lcm(B, G) + 1
    # print(r, rest, x, ans)

print(ans)


### FIXED CODE ###

def inpl():
    return list(map(int, input().split()))


def gcd(a, b):
    # greatest common divisor
    la = max(a, b)
    sm = min(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la - sm)


def lcm(a, b):
    # least common multiple
    return a * b // gcd(a, b)

import sys

sys.setrecursionlimit(5000)


R, G, B, N = inpl()
ans = 0
for r in range(N // R + 1):
    rest = N - r * R
    for i in range(B):
        if (G * i) % B == rest % B:
            x = i
            break
    else:
        # print(r)
        continue
    if rest - G * x < 0:
        continue
    ans += (rest - G * x) // lcm(B, G) + 1
    # print(r, rest, x, ans)

print(ans)
n = int(input())
a = [int(i) for i in input().split()]
s0 = a[0]
count=0

i=0
while a[i]!=0:i++
if a[i]>0:
  s0+=1
  count+=1
else:
  s0-=1
  count+=1
  

  for i in range(1,n):
  s1 = s0+a[i]
  if s0*s1>=0:
    if s1>0:
      a[i]-=(abs(s1)+1)
      count+=(abs(s1)+1)
    elif s1<0:
      a[i]+=(abs(s1)+1)
      count+=(abs(s1)+1)
    elif s1==0:
      if s0>0:
        a[i]-=1
        count+=1
      elif s0<0:
        a[i]+=1
        count+=1
  s0 += a[i]
print(count)

### FIXED CODE ###

import copy
n = int(input())
a = [int(i) for i in input().split()]
b=a.copy()
s0p = a[0]
s0n = b[0]
countp = 0
countn = 0

if a.count(0)==n:
  print(2*n-1)
  exit()

if s0p<=0:
  s0p+=(abs(a[0])+1)
  countp+=(abs(a[0])+1)
  
if s0n>=0:
  s0n-=(abs(b[0])+1)
  countn+=(abs(b[0])+1)

for i in range(1,n):
  s1 = s0p+a[i]
  if s0p*s1>=0:
    if s1>0:
      a[i]-=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1<0:
      a[i]+=(abs(s1)+1)
      countp+=(abs(s1)+1)
    elif s1==0:
      if s0p>0:
        a[i]-=1
        countp+=1
      elif s0p<0:
        a[i]+=1
        countp+=1
  s0p += a[i]

for i in range(1,n):
  s1 = s0n+b[i]
  if s0n*s1>=0:
    if s1>0:
      b[i]-=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1<0:
      b[i]+=(abs(s1)+1)
      countn+=(abs(s1)+1)
    elif s1==0:
      if s0n>0:
        b[i]-=1
        countn+=1
      elif s0n<0:
        b[i]+=1
        countn+=1
  s0n += b[i]
  
print(countp if countp<=countn else(countn))
n = int(input())
 
for i in range(n//4+1):
    for j in range(n//7+1):
        if n == 4*i+7*j:
            print('Yes')
            exit(0)
print('No')

### FIXED CODE ###

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

ans = 0
if n % k == 0:
    ans = 0
else:
    ans = 1

print(str(ans))
b = s[:m]

for i in range(int(m/2)):
    if b[i:(i+1)] != b[(m-i-1):m-i]:
        print('No')
        sys.exit()
m = int((n+3)/2)
b = s[m-1:]
m= len(b)
for i in range(int(m/2)):
    if b[i:(i+1)] != b[(m-i-1):m-i]:
        print('No')
        sys.exit()
print('Yes')

### FIXED CODE ###

import sys
s = input()

n = len(s)
m = int((n-1)/2)
b = s[:m]

for i in range(int(m/2)):
    if b[i:(i+1)] != b[(m-i-1):m-i]:
        print('No')
        sys.exit()
m = int((n+3)/2)
b = s[m-1:]
m= len(b)
for i in range(int(m/2)):
    if b[i:(i+1)] != b[(m-i-1):m-i]:
        print('No')
        sys.exit()
for i in range(int(n/2)):
    if s[i:(i+1)] != s[(n-i-1):n-i]:
        print('No')
        sys.exit()  
print('Yes')
n=int(input())
p=list(map(int, input().solilt()))
c=0
for i in range(1,n-1):
    if (p[i-1]<p[i] and p[i]<p[i+1]) or (p[i-1]>p[i] and p[i]>p[i+1]):
        c+=1
print(c)
        

### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
c=0
for i in range(1,n-1):
    if (p[i-1]<p[i] and p[i]<p[i+1]) or (p[i-1]>p[i] and p[i]>p[i+1]):
        c+=1
print(c)
a, b, h = map(int, input().split())
print((a + b) * h // 2)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print(int((a + b) * h / 2))