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

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

dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    pi = p[i]
    dp[i + 1][0] = dp[i][0] * pi
    for j in range(i + 1):
        dp[i + 1][j + 1] = dp[i][j + 1] * pi + dp[i][j] * (1 - pi)
print(sum(dp[-1][:n // 2 + 1]))


### FIXED CODE ###

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

dp = [0 for j in range(n + 1)]
dp[0] = 1
for i in range(n):
    pi = p[i]
    for j in range(i, -1, -1):
        dp[j + 1] = dp[j + 1] * pi + dp[j] * (1 - pi)
    dp[0] *= pi
print(sum(dp[:n // 2 + 1]))
### BUGGY CODE ###

from sys import stdin
from queue import Queue
 
 
def main():
    n, x, y = [int(x) for x in stdin.readline().rstrip().split()]
    x -= 1
    y -= 1
    ans = [0] * n
    for i in range(n):
        dist = [None] * n
        q = Queue()
 
        def push(d, v):
            if v < 0 or n <= v:
                return
            if dist[v] is not None:
                return
            dist[v] = d
            q.put(v)
 
        push(0, i)
        while not q.empty():
            v = q.get()
            d = dist[v]
            push(d + 1, v - 1)
            push(d + 1, v + 1)
            if v == x:
                push(d + 1, y)
            if v == y:
                push(d + 1, x)
 
        for d in dist:
            ans[d] += 1
 
    ans = [x // 2 for x in ans]
    print(*ans[1:], sep='\n')
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin


def main():
    N, X, Y = [int(x) for x in stdin.readline().rstrip().split()]
    result = [0] * (N - 1)
    for left in range(1, N):
        for right in range(left + 1, N + 1):
            if (left <= X) and (Y <= right):
                x = (X - left) + 1 + (right - Y)
            elif (left <= X) and (X <= right <= Y):
                x = (X - left) + min((right - X), (Y - right) + 1)
            elif (X <= left <= Y) and (Y <= right):
                x = min((Y - left), (left - X) + 1) + (right - Y)
            elif (X <= left <= Y) and (X <= right <= Y):
                x = min((right - left), (left - X) + (Y - right) + 1)
            else:
                x = right - left
            result[x - 1] += 1
    print(*result, sep='\n')


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

A, B, N = [int(x) for x in input().split()]
max_val = 0
for x in range(N+1):
  if (A*x)//B -A*(x//B) > max_val:
    max_val = (A*x)//B -A*(x//B)
print(max_val)

### FIXED CODE ###

A, B, N = [int(x) for x in input().split()]
max_val = 0
j = min(B-1,N)
x = (A*j)//B - A*(j//B)
print(x)
### BUGGY CODE ###

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100040
inv = [1] * 100040
for k in range(1, 100040):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2)

ans = 1
for e in f:
    ans = ans * fact[e+N-1] % mod * inv[e] % mod * inv[N-1] % mod # N_H_e (重複組合せ)

print(ans)


### FIXED CODE ###

from collections import Counter

mod = 1000000007

# nの素因数分解

def prime(n):
    d = Counter()
    i = 2
    while i*i <= n:
        while n%i == 0:
            n //= i
            d[i] += 1
        i += 1
    if n > 1:
        d[n] += 1
    return d

# xのn乗を計算する
def mod_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half_x = mod_pow(x, n // 2)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n-1) % mod

fact = [1] * 100100
inv = [1] * 100100
for k in range(1, 100100):
    fact[k] = fact[k-1] * k % mod
    inv[k] = mod_pow(fact[k], mod-2)

def nCr(n, r):
    return fact[n] * inv[r] % mod * inv[n-r] % mod

def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p.values():
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)

solve()
### BUGGY CODE ###

from itertools import combinations
s = input()
n = len(s)
k = int(input())
ij = list(combinations(range(n+1), 2))
#print(ij)
substr = []
for i, j in ij:
    if j > i+k:
        continue
    sub = s[i:j]
    if sub not in substr:
        substr.append(s[i:j])
substr.sort()
print(substr[k-1])


### FIXED CODE ###


s = input()
n = len(s)
k = int(input())
substr = []
for j in range(k):
    for i in range(n-j):
        sub = s[i:i+j+1]
        if sub not in substr:
            substr.append(sub)
substr.sort()
print(substr[k-1])
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(input()) for _ in range(n)]
h.sort()
l=[]
for i in range(n-k+1):
    l.append(max(h[i:i+k])-min(h[i:i+k]))
print(min(l))

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for _ in range(n)]
h.sort()
l=[]
for i in range(n-k+1):
    l.append(h[i+k-1] - h[i])
print(min(l))
### BUGGY CODE ###

import itertools
N = int(input())
S = input()
comb = list(itertools.combinations(list(range(N)),3))
ans = []
for i in comb:
    pw = []
    for j in range(len(comb[0])):
        pw.append(S[i[j]])
    pw = "".join(pw)
    if pw not in ans:
        ans.append(pw)
print(len(ans))

### FIXED CODE ###

N = int(input())
S = list(input())
pas = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            pas.append(str(i)+str(j)+str(k))
ans = 0
for pw in pas:
    if pw[0] in S:
        ind = S.index(pw[0])
        tmp = S[ind+1:]
    else:
        continue
    if pw[1] in tmp:
        ind = tmp.index(pw[1])
        tmp = tmp[ind+1:]
    else:
        continue
    if pw[2] in tmp:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]

for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]

for i in range(h * w-d):
    num[i%d][i//d] = abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(sum(num[now % d - 1][(now - now % d) // d-1:(goal - now % d) // d-1]))
    else:
        print(sum(num[now%d-1][(now-now%d)//d:(goal-now%d)//d]))

### FIXED CODE ###

import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]

for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]

for i in range(h * w-d):
    num[i%d][i//d+1] = num[i%d][i//d]+abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(num[now%d-1][(goal-now%d)//d-1]-num[now%d-1][(now-now%d)//d-1])
    else:
        print(num[now%d-1][(goal-now%d)//d]-num[now%d-1][(now-now%d)//d])
### BUGGY CODE ###

import math

a, b, n = map(int, input().split())
ans = 0
tmp = 0

for x in range(1, n+1):
    tmp = math.floor(a*x/b) - a*math.floor(x/b)
    if tmp >= ans:
        ans = tmp

print(ans)

### FIXED CODE ###

import math

a, b, n = map(int, input().split())
ans = 0
tmp = 0

if n > b - 1:
    n = b-1

ans = math.floor(a*n/b) - a*math.floor(n/b)

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

from collections import Counter
from math import factorial

S = input()
S = list(map(int, S))

nums = S[::-1]
for i in range(1, len(nums)):
    nums[i] = nums[i - 1] + nums[i] * 10 ** i

nums = [0] + [n % 2019 for n in nums]

counter = Counter(nums)
ans = 0
for count in counter.values():
    if count >= 2:
        ans += factorial(count) // (factorial(count - 2) * factorial(2))

print(ans)


### FIXED CODE ###

S = input()
S = list(map(int, S))

t = 1
r = 0
d = [0] * 2019
d[0] += 1
for n in reversed(S):
    r = (r + n * t) % 2019
    t = t * 10 % 2019
    d[r] += 1

ans = 0
for m in d:
    ans += m * (m-1) // 2

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

print(sum(range(int(input()))))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###


N = int(input())
words = [input() for i in range(N)] 

ans = 0
for ix, word in  enumerate(words):
    for j, compe_word in enumerate(words[ix+1:]):
        compe_word_list = list(compe_word)
        for alphabet in word:
            if alphabet in compe_word_list:
                compe_word_list.pop(compe_word_list.index(alphabet))
        if len(compe_word_list) == 0:
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
dic = {}

for i in range(N):
    spell = ''.join(sorted(input()))
    if spell in dic.keys():
        dic[spell] += 1
    else:
        dic[spell] = 1

count = 0
for num in dic.values():
    count += sum([i for i in range(num)])

print(count)
### BUGGY CODE ###

L, R = map(int, input().split())
min_mod = 10**9
for i in range(L, R):
    for j in range(i + 1, R + 1):
        min_mod = min(min_mod, (i * j) % 2019)
print(min_mod)


### FIXED CODE ###

L, R = map(int, input().split())
min_mod = 10**9
for i in range(L, min(L + 2019, R + 1)):
    for j in range(i + 1, min(L + 2019, R + 1)):
        min_mod = min(min_mod, (i * j) % 2019)
print(min_mod)
### BUGGY CODE ###

h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]

inf = float('inf')
memo = [inf for _ in range(10**5)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        memo[i+x] = min(memo[i+x],memo[i] + y)
print(min(memo[h:h+10000]))

### FIXED CODE ###

h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]
 
inf = float('inf')
memo = [inf for _ in range(h+1)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        j = min(i+x, h)
        memo[j] = min(memo[j],memo[i] + y)
print(memo[-1])
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

for i in range(m):
    a,b = map(int, input().split())
    ns[a-1].add(b-1)

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                if ns[u]&us-set([nu]):
                    for v in ns[u]&us-set([nu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update or len(us)==len(hist):
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

for i in range(m):
    a,b = map(int, input().split())
    ns[a-1].add(b-1)

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
def cycle(hist, pos):
    for i, u in enumerate(hist):
        if u==pos:
            break
    return hist[i:]

for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        hist = cycle(hist, pos)
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                pu = hist[(i-1)]
                if (ns[u]&us)-set([nu, pu]):
                    for v in (ns[u]&us)-set([nu, pu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update:
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)
### BUGGY CODE ###

n = int(input())

game = [0]

for _ in range(n):
    comp = list(map(int, input().split()))
    game.append(comp[::-1])

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = set()
    possible = False
    for me in range(1, n+1):
        if me in finish or game[me] == []:
            continue

        you = game[me][-1]
        if you in finish or game[you] == []:
            continue
        else:
            if game[you][-1] == me:
                finish.add(game[you].pop())
                finish.add(game[me].pop())
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

S = input()

def check(s):
  if len(s) >= 5 and (s[-5:] == 'erase' or s[-5:] == 'dream'):
    return check(s[:-5])
  elif len(s) >= 6 and s[-6:] == 'eraser':
    return check(s[:-6])
  elif len(s) >= 7 and s[-7:] == 'dreamer':
    return check(s[:-7])
  elif len(s) == 0:
    return True
  else:
    return False

print('YES' if check(S) else 'NO')

### FIXED CODE ###

S = input()

def check(t):
  if len(t) >= 5 and (t[-5:] == 'dream' or t[-5:] == 'erase'):
    return True,t[:-5]
  elif len(t) >=6 and t[-6:] == 'eraser':
    return True,t[:-6]
  elif len(t) >= 7 and t[-7:] == 'dreamer':
    return True,t[:-7]
  else:
    return False,t

while(len(S) > 0):
  flag,S = check(S)
  if not flag:
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

s=[1 if i=="R" else -1 for i in input()]
n=len(s)
k=10**100
a=[i+s[i] for i in range(n)]
while k:
  a=[a[i] for i in a]
  k >>= 1
print(*[a.count(i) for i in range(n)])

### FIXED CODE ###

s=input()
ans=[0]*len(s)
cnt=1
for i in range(1,len(s)):
  if s[i]=='R':
    cnt+=1
  else:
    ans[i-1]+=(cnt+1)//2
    ans[i]+=cnt-(cnt+1)//2
    cnt=0
cnt=1
for i in range(len(s)-1)[::-1]:
  if s[i]=='L':
    cnt+=1
  else:
    ans[i+1]+=(cnt+1)//2
    ans[i]+=cnt-(cnt+1)//2
    cnt=0
print(' '.join(map(str,ans)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = input().split()
b = []
for i in range(n):
    b.append(a[i])
    b.reverse()
print(' '.join(b))

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
a = [x for x in sys.stdin.readline().split()]
b = [a[i] for i in range(n) if i % 2 != 0]
rb = b[::-1]
c = [a[i] for i in range(n) if i % 2 == 0]
rc = c[::-1]

if n % 2 == 0:
    ans = rb + c
else:
    ans = rc + b

ans = " ".join(ans)
print(ans)
### BUGGY CODE ###

import sys
X = list(sys.stdin.readline().strip())
N = len(X)

def solve():
    cnt = 0
    i = 0
    while True:
        while i < N and X[i] != 'S':
            i += 1
        j = i
        while j < N and X[j] != 'T':
            j += 1
        if j >= N:
            return N - 2*cnt
        cnt += 1
        if 2*cnt == N:
            return 0
        X[i] = ' '
        X[j] = ' '
        i += 1
        j += 1

print(solve())

### FIXED CODE ###

X = list(input())
N = len(X)
NHALF = N // 2

def solve():
    nt, ns = 0, 0
    for i in range(N):
        if X[i] == 'S':
            ns += 1
        elif ns > 0:
            ns -= 1
        else:
            nt += 1
    return nt + ns


print(solve())
### BUGGY CODE ###

n=int(input())
numeros=[int (x) for x in input().split()]
qtd=[]
K=1
cont2=0
while True:
    cont=0
    cont1=0
    for num in numeros:
        if num<K:
            cont+=1
        else:
            cont1+=1
    if cont==cont1:
        cont2+=1
    K+=1
    if K>max(numeros):
        break
print(cont2)

### FIXED CODE ###

k = int(input())
seqS=input().split(" ")
num=[]
for q in seqS:
    num.append(int(q))
contador,abc,arc=0,0,0
num.sort() #ORGANIZA
#num do meio
print(num[int(len(num)/2)]- num[int(len(num)/2)-1])
### BUGGY CODE ###

h,w = map(int,input().split())
s = []
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(h):
    s += [input()]
ans = 0


def dfs(d, i, j, c):
    if i < 0 or h <= i or j < 0 or w <= j:
        return
    if s[i][j] == '#' or d[i][j] <= c:
        return

    d[i][j] = c
    for y,x in v:
        dfs(d, i+y, j+x, c+1)


for i in range(h*w):
    for j in range(h*w):
        d = [[h * w] * w for i in range(h)]
        p = (i // w, i % w)
        q = (j // w, j % w)
        if s[p[0]][p[1]] == '#' or s[q[0]][q[1]] == '#':
            continue
        dfs(d, p[0], p[1], 0)
        if d[q[0]][q[1]] < h*w:
            ans = max(d[q[0]][q[1]], ans)

print(ans)

### FIXED CODE ###

import queue
h,w = map(int,input().split())
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [input() for i in range(h)]

ans = 0
que = queue.Queue()
for i in range(h * w):
    c = 0
    d = [[h*w] * w for i in range(h)]
    p = (i//w, i%w)
    if s[p[0]][p[1]] == '#':
        continue
    d[p[0]][p[1]] = 0
    que.put(p)
    while not que.empty():
        y,x = que.get()
        c = d[y][x]
        for dy, dx in v:
            yy = y + dy
            xx = x + dx
            if yy < 0 or xx < 0 or h <= yy or w <= xx:
                continue
            if s[yy][xx] == '#':
                continue
            if d[yy][xx] < h*w:
                continue
            que.put((yy, xx))
            d[yy][xx] = c + 1
    ans = max(ans, c)
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# D以下orUより大きい場所への遷移
def to0or4(base: int, nex: int):
    return base + nex

# Dより大きくS以下 or Gより大きくU以下の場所への遷移
def to1or3(base: int, nex: int):
    if nex == 0:
        return base + 2
    
    elif nex % 2:
        return base + 1
    
    else:
        return base


# Sより大きくG以下の場所への遷移
def to2(base: int, nex: int):
    if nex % 2:
        return base
    
    else:
        return base + 1
    
n = ni()
a = [ni() for _ in range(n)]
suma = sum(a)  

# 配るDP
dp = [[suma]*5 for _ in range(n+1)]
dp[0] = [0]*5

for i in range(n):
    for idx in range(5):
        for jdx in range(idx,5):
            
            if jdx == 0 or jdx == 4:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to0or4(dp[i][idx], a[i]))
            
            elif jdx == 1 or jdx == 3:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to1or3(dp[i][idx], a[i]))
                
            elif jdx == 2:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to2(dp[i][idx], a[i]))
   
print(min(dp[n]))

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

# D以下orUより大きい場所への遷移
def to0or4(base: int, nex: int):
    return base + nex

# Dより大きくS以下 or Gより大きくU以下の場所への遷移
def to1or3(base: int, nex: int):
    if nex == 0:
        return base + 2
    
    elif nex % 2:
        return base + 1
    
    else:
        return base


# Sより大きくG以下の場所への遷移
def to2(base: int, nex: int):
    if nex % 2:
        return base
    
    else:
        return base + 1
    
n = ni()
a = [ni() for _ in range(n)]
suma = sum(a)  

# 配るDP
dp = [[suma]*5 for _ in range(n+1)]
dp[0] = [0]*5

for i in range(n):
    for idx in range(5):
        for jdx in range(idx,5):
            
            if jdx == 0 or jdx == 4:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to0or4(dp[i][idx], a[i]))
            
            elif jdx == 1 or jdx == 3:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to1or3(dp[i][idx], a[i]))
                
            elif jdx == 2:
                dp[i+1][jdx] = min(dp[i+1][jdx],
                                   to2(dp[i][idx], a[i]))
   
print(min(dp[n]))
### BUGGY CODE ###

x,y = input().split()
x = int(x)
y = int(y)
while True:
    if x < y:
        print(y,x)
    if x > y:
        print(x,y)
    if x==0 and y==0:
        break
    


### FIXED CODE ###


while True:
    x,y = input().split()
    x = int(x)
    y = int(y)
    if x==0 and y==0:
        break
    elif x<y:
        print(x,y)
    elif x>=y:
        print(y,x)