Scientists say a lot about the problems of global warming and cooling of the Earth. Indeed, such natural phenomena strongly influence all life on our planet.

Our hero Vasya is quite concerned about the problems. He decided to try a little experiment and observe how outside daily temperature changes. He hung out a thermometer on the balcony every morning and recorded the temperature. He had been measuring the temperature for the last n days. Thus, he got a sequence of numbers t_1, t_2, ..., t_{n}, where the i-th number is the temperature on the i-th day.

Vasya analyzed the temperature statistics in other cities, and came to the conclusion that the city has no environmental problems, if first the temperature outside is negative for some non-zero number of days, and then the temperature is positive for some non-zero number of days. More formally, there must be a positive integer k (1 ≤ k ≤ n - 1) such that t_1 < 0, t_2 < 0, ..., t_{k} < 0 and t_{k} + 1 > 0, t_{k} + 2 > 0, ..., t_{n} > 0. In particular, the temperature should never be zero. If this condition is not met, Vasya decides that his city has environmental problems, and gets upset.

You do not want to upset Vasya. Therefore, you want to select multiple values of temperature and modify them to satisfy Vasya's condition. You need to know what the least number of temperature values needs to be changed for that.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of days for which Vasya has been measuring the temperature. 

The second line contains a sequence of n integers t_1, t_2, ..., t_{n} (|t_{i}| ≤ 10^9) — the sequence of temperature values. Numbers t_{i} are separated by single spaces.


-----Output-----

Print a single integer — the answer to the given task.


-----Examples-----
Input
4
-1 1 -2 1

Output
1

Input
5
0 -1 1 2 -5

Output
2



-----Note-----

Note to the first sample: there are two ways to change exactly one number so that the sequence met Vasya's condition. You can either replace the first number 1 by any negative number or replace the number -2 by any positive number.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Implementation


Solutions:
f = open('input.txt', 'r')
n = int(f.readline())
arr = list(map(int, f.readline().split()))
cntP = [0] * (n + 1)
for i in range(1, n):
	cntP[i] = cntP[i - 1] + (arr[i - 1] >= 0)
cntN = [0] * (n + 1)
for i in range(n - 2, -1, -1):
	cntN[i] = cntN[i + 1] + (arr[i + 1] <= 0)
res = 2000000000.0
for i in range(n - 1):
	res = min(res, cntP[i + 1] + cntN[i])
print(res, file=open('output.txt', 'w'))


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = int(input())
l = list(map(int, input().split()))
neg = [0] * n
pos = [0] * n
if l[0] >= 0:
	pos[0] = 1
for i in range(1, n):
	if l[i] >= 0:
		pos[i] = pos[i - 1] + 1
	else:
		pos[i] = pos[i - 1]
if l[-1] <= 0:
	neg[-1] = 1
for i in range(n - 2, -1, -1):
	if l[i] <= 0:
		neg[i] = neg[i + 1] + 1
	else:
		neg[i] = neg[i + 1]
ans = float('inf')
for i in range(n - 1):
	ans = min(ans, pos[i] + neg[i + 1])
print(ans)


f = open('input.txt', 'r')
(n, a) = (int(f.readline()), list(map(int, f.readline().split())))
(an, ap) = ([0] * n, [0] * n)
for i in range(1, n):
	an[i] = an[i - 1] + (a[i - 1] >= 0)
for i in range(n - 2, -1, -1):
	ap[i] = ap[i + 1] + (a[i + 1] <= 0)
print(min((an[i + 1] + ap[i] for i in range(n - 1))), file=open('output.txt', 'w'))


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split()]
front = [0] * (len(a) + 2)
for i in range(n):
	front[i + 1] = front[i] + (1 if a[i] >= 0 else 0)
back = [0] * (len(a) + 2)
for i in range(n - 1, -1, -1):
	back[i + 1] = back[i + 2] + (1 if a[i] <= 0 else 0)
ans = len(a) + 1
for i in range(1, n):
	ans = min(ans, front[i] + back[i + 1])
print('%d' % ans)


import sys
infile = open('input.txt', 'r')
outfile = open('output.txt', 'w+')
sys.stdin = infile
sys.stdout = outfile
n = int(input())
t = list(map(int, input().split()))
dp = [[0] * 2 for _ in range(n + 1)]
for i in range(n):
	dp[i + 1] = dp[i][:]
	if t[i] >= 0:
		dp[i + 1][0] += 1
	if t[i] <= 0:
		dp[i + 1][1] += 1
ans = n
for i in range(0, n - 1):
	ans = min(ans, dp[i + 1][0] - dp[0][0] + dp[n][1] - dp[i + 1][1])
print(ans)


import sys
from collections import *
import os.path
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	pref_pos = [0 for i in range(n)]
	suf_neg = [0 for i in range(n)]
	(a, b) = (INF, -INF)
	for i in range(n):
		if l[i] >= 0:
			if i == 0:
				pref_pos[i] = 1
			else:
				pref_pos[i] = 1 + pref_pos[i - 1]
		elif i != 0:
			pref_pos[i] += pref_pos[i - 1]
		if l[n - i - 1] <= 0:
			if i == 0:
				suf_neg[n - i - 1] = 1
			else:
				suf_neg[n - 1 - i] = 1 + suf_neg[n - i]
		elif i != 0:
			suf_neg[n - i - 1] += suf_neg[n - i]
		a = min(a, l[i])
		b = max(b, l[i])
	if a > 0 and b > 0 or (a < 0 and b < 0):
		pr(1)
		return
	ans = INF
	for i in range(n - 1):
		ans = min(ans, pref_pos[i] + suf_neg[i + 1])
	pr(ans)
solve()


f = open('output.txt', 'w+')
I = open('input.txt', 'r')
n = int(I.readline())
a = list(map(int, I.readline().split()))
b = [0] * n
cc = 0
for i in range(n - 1, -1, -1):
	if a[i] <= 0:
		cc += 1
	b[i] = cc
cc = 0
ans = n + 1
for i in range(0, n - 1):
	if a[i] >= 0:
		cc += 1
	ans = min(ans, cc + b[i + 1])
f.write(str(ans))


from sys import stdin
input = stdin.readline
file = open('input.txt', 'r')
num = file.readlines()
file.close()
n = int(num[0])
arr = [int(x) for x in num[1].split()]
f = [0] * (n + 1)
b = [0] * (n + 1)
ans = 1e+18
for i in range(1, n + 1):
	if arr[i - 1] >= 0:
		f[i] = f[i - 1] + 1
	else:
		f[i] = f[i - 1]
f.pop(0)
for i in range(n - 1, -1, -1):
	if arr[i] <= 0:
		b[i] = b[i + 1] + 1
	else:
		b[i] = b[i + 1]
for i in range(n - 1):
	ans = min(ans, f[i] + b[i + 1])
with open('output.txt', 'a') as file:
	file.write('%d\n' % ans)


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(input())
y = 0
ans = 10 ** 9
l = [int(i) for i in input().split()]
x = sum((i <= 0 for i in l))
for i in range(n):
	if l[i] <= 0:
		x -= 1
	if l[i] >= 0:
		y += 1
	if i == n - 1 and l[i] <= 0:
		x += 1
	ans = min(ans, x + y)
print(ans)


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(input())
l = list(map(int, input().split()))
a = [0 for i in range(n)]
b = [0 for i in range(n)]
if l[0] >= 0:
	a[0] = 1
for i in range(1, n):
	if l[i] >= 0:
		a[i] = a[i - 1] + 1
	else:
		a[i] = a[i - 1]
for i in range(n - 2, -1, -1):
	if l[i + 1] <= 0:
		b[i] = b[i + 1] + 1
	else:
		b[i] = b[i + 1]
ans = n
for i in range(n - 1):
	ans = min(ans, a[i] + b[i])
print(ans)


R = lambda : map(int, input().split())
f = open('input.txt', 'r')
(n, arr) = (int(f.readline()), list(map(int, f.readline().split())))
dp = [0] * n
for i in range(n):
	dp[i] = dp[i - 1] + (1 if arr[i] >= 0 else 0)
acc = 0
res = n
for i in range(n - 2, -1, -1):
	acc += 1 if arr[i + 1] <= 0 else 0
	res = min(res, acc + dp[i])
print(res, file=open('output.txt', 'w'))


from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def solve():
	n = ii()
	a = li()
	pos = [0] * n
	neg = [0] * n
	if a[0] > 0:
		pos[0] = 1
	if a[0] < 0:
		neg[0] = 1
	for i in range(1, n):
		pos[i] = pos[i - 1]
		neg[i] = neg[i - 1]
		if a[i] > 0:
			pos[i] += 1
		if a[i] < 0:
			neg[i] += 1
	ans = n
	count0 = a.count(0)
	for i in range(1, n - 1):
		ans = min(ans, pos[i - 1] + neg[n - 1] - neg[i])
	print(ans + count0)
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
solve()


import sys
inf = float('inf')
mod = 1000000007
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return list(map(int, sys.stdin.readline().split()))

def input():
	return sys.stdin.readline()

def __starting_point():
	n = int(input())
	arr = get_array()
	count_f = [0] * (n + 2)
	for i in range(1, n + 1):
		x = 0
		if arr[i - 1] >= 0:
			x = 1
		count_f[i] = count_f[i - 1] + x
	count_b = [0] * (n + 2)
	for i in range(n, 0, -1):
		x = 0
		if arr[i - 1] <= 0:
			x = 1
		count_b[i] = count_b[i + 1] + x
	ans = n
	for i in range(1, n):
		if count_f[i] + count_b[i + 1] < ans:
			ans = count_f[i] + count_b[i + 1]
	print(ans)
__starting_point()


with open('input.txt', 'r') as g:
	n = int(g.readline())
	lst = list(map(int, g.readline().split()))
	(x, y) = (0, 0)
	for (i, e) in enumerate(lst):
		if e <= 0:
			y += 1
	mn = 10 ** 9
	for i in range(1, n):
		if lst[i - 1] > 0:
			x += 1
		if lst[i - 1] < 0:
			y -= 1
		if x + y < mn:
			mn = x + y
with open('output.txt', 'w') as d:
	d.write(str(mn))


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(input())
t = list(map(int, input().split()))
l = []
r = [0] * (n - 1)
p = m = 0
for i in range(n - 1):
	if t[i] > -1:
		p += 1
	l.append(p)
for i in range(n - 1, 0, -1):
	if t[i] < 1:
		m += 1
	r[i - 1] = m
mn = float('+inf')
for i in range(n - 1):
	mn = min(mn, l[i] + r[i])
print(mn)


from collections import defaultdict
nums = None
with open('input.txt') as f:
	n = next(f)
	line = next(f)
	nums = [int(i) for i in line.split()]
non_neg = defaultdict(int)
non_pos = defaultdict(int)
for (i, num) in enumerate(nums):
	if num >= 0:
		non_neg[i] = non_neg[i - 1] + 1
	else:
		non_neg[i] = non_neg[i - 1]
for i in range(len(nums) - 1, -1, -1):
	num = nums[i]
	if num <= 0:
		non_pos[i] = 1 + non_pos[i + 1]
	else:
		non_pos[i] = non_pos[i + 1]
res = float('inf')
for (i, num) in enumerate(nums[:len(nums) - 1]):
	res = min(non_neg[i] + non_pos[i + 1], res)
with open('output.txt', 'a') as f:
	f.write(str(res))


with open('input.txt', 'r') as f:
	n = int(f.readline())
	temp = [int(t) for t in f.readline().split()]
count_pos_left = []
n_pos_left = 0
for i in range(0, n):
	count_pos_left.append(n_pos_left)
	if temp[i] >= 0:
		n_pos_left += 1
count_neg_right = []
n_neg_right = 0
for i in range(n - 1, -1, -1):
	count_neg_right.append(n_neg_right)
	if temp[i] <= 0:
		n_neg_right += 1
count_neg_right.reverse()
ans = n
for i in range(1, n - 1):
	ans = min(ans, count_pos_left[i] + count_neg_right[i] + (1 if temp[i] == 0 else 0))
ans = min(ans, count_neg_right[0] + (1 if temp[0] >= 0 else 0))
ans = min(ans, count_pos_left[n - 1] + (1 if temp[n - 1] <= 0 else 0))
with open('output.txt', 'w') as f:
	f.write(str(ans))


R = lambda : map(int, input().split())
f = open('input.txt', 'r')
n = int(f.readline())
L = list(map(int, f.readline().split()))
T = []
c = 0
for i in range(n):
	T.append([c])
	if L[i] >= 0:
		c += 1
c = 0
for i in reversed(range(n)):
	T[i].append(c)
	if L[i] <= 0:
		c += 1
res = 10 ** 9
if L[0] > 0:
	T[0][0] += 1
if L[n - 1] < 0:
	T[n - 1][1] += 1
for i in range(n):
	k = sum(T[i])
	if L[i] == 0:
		k += 1
	res = min(res, k)
open('output.txt', 'w').write(str(res))


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(input())
r = sys.maxsize
t = list(map(int, input().split()))
l1 = [0] * (n + 1)
l2 = [0] * (n + 1)
for (i, j) in enumerate(t):
	l1[i + 1] = l1[i] + (0 if j < 0 else 1)
	l2[i + 1] = l2[i] + (0 if j > 0 else 1)
for k in range(1, n):
	r = min(r, l1[k] + l2[n] - l2[k])
print(r)


fin = open('input.txt', 'r')
fout = open('output.txt', 'w')
n = int(fin.readline())
a = [int(i) for i in fin.readline().split()]
plus = [0] * (n + 1)
minus = [0] * (n + 1)
zero = [0] * (n + 1)
for i in range(n):
	if a[i] < 0:
		plus[i + 1] = plus[i]
		minus[i + 1] = minus[i] + 1
		zero[i + 1] = zero[i]
	elif a[i] > 0:
		plus[i + 1] = plus[i] + 1
		minus[i + 1] = minus[i]
		zero[i + 1] = zero[i]
	else:
		plus[i + 1] = plus[i]
		minus[i + 1] = minus[i]
		zero[i + 1] = zero[i] + 1
best = float('inf')
for i in range(n - 1):
	x = plus[i + 1] + minus[-1] - minus[i + 1] + zero[-1]
	best = min(best, x)
print(best, file=fout)
fin.close()
fout.close()


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
n = int(sys.stdin.readline()) - 2
t = [int(x) for x in sys.stdin.readline().split()]
s = int(t[0] >= 0) + int(t[-1] <= 0)
if n:
	(t, p) = (t[1:-1], [0] * n)
	x = 0
	for i in range(n):
		if t[i] < 0:
			x += 1
		p[i] = x
	t.reverse()
	p.reverse()
	x = 0
	for i in range(n):
		if t[i] > 0:
			x += 1
		p[i] += x
	print(s + n - max(p))
else:
	print(s)


with open('input.txt', 'r') as f:
	n = int(f.readline())
	t = list(map(int, f.readline().split()))
m = 0
for i in range(1, n):
	if t[i] <= 0:
		m += 1
if t[0] >= 0:
	m += 1
p = m
for i in range(1, n - 1):
	if t[i] < 0:
		cost = -1
	elif t[i] == 0:
		cost = 0
	else:
		cost = 1
	p += cost
	m = min(m, p)
with open('output.txt', 'w') as f:
	f.write(str(m))


f = open('input.txt', 'r')
fContent = f.readlines()
f.close()
n = int(fContent[0])
temperatures = list(map(int, fContent[1].split()))
zeros = 0
pos = 0
neg = 0
for x in temperatures:
	if x < 0:
		neg += 1
	elif x > 0:
		pos += 1
	else:
		zeros += 1
changes = 99999999999
leftPos = 0
leftNeg = 0
for i in range(len(temperatures) - 1):
	if temperatures[i] < 0:
		leftNeg += 1
	elif temperatures[i] > 0:
		leftPos += 1
	changes = min(changes, leftPos + zeros + (neg - leftNeg))
outF = open('output.txt', 'w+')
outF.write(str(changes))
outF.close()


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : list(map(int, input().split()))
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
l = il()
lf = [0] * n
lf[0] = 1 if l[0] >= 0 else 0
lb = [0] * n
lb[-1] = 1 if l[-1] <= 0 else 0
for i in range(1, n):
	if l[i] >= 0:
		lf[i] = lf[i - 1] + 1
	else:
		lf[i] = lf[i - 1]
for i in range(n - 2, -1, -1):
	if l[i] <= 0:
		lb[i] = lb[i + 1] + 1
	else:
		lb[i] = lb[i + 1]
mn = 10 ** 10
for i in range(n - 1):
	mn = min(mn, lf[i] + lb[i + 1])
print(mn)


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
mod = 1000000007
get_arr = lambda : list(map(int, input().split()))
get_int = lambda : int(input())
get_ints = lambda : map(int, input().split())
get_str = lambda : input()
get_strs = lambda : input().split()
n = get_int()
A = get_arr()
(pos, neg, ans, temp) = (0, 0, sys.maxsize, 0)
for i in range(n - 1):
	if A[i] <= 0:
		neg += 1
if A[-1] <= 0:
	temp += 1
for i in range(n - 1):
	if A[i] <= 0:
		neg -= 1
	if A[i] >= 0:
		pos += 1
	ans = min(ans, pos + neg)
print(ans + temp)