15. Make the Array Beautiful

Difficulty: easy · Array, Greedy

Problem

An array of non-zero integers is called **beautiful** if the signs of adjacent elements alternate: every positive element is next to negative elements only, and every negative element is next to positive elements only. In one operation you may pick any element and multiply it by `-1`. Find the minimum number of operations needed to make the array beautiful.

Input

- Line 1: the integer `n`. - Line 2: `n` space-separated non-zero integers.

Output

Print the minimum number of operations.

Example 1

Input:
5
-1 3 -2 4 5
Output:
1

Explanation: The signs are - + - + +. Flipping only the last element gives - + - + -, so 1 operation is enough.

Example 2

Input:
4
1 2 3 4
Output:
2

Explanation: Pattern + - + - needs 2 flips (2 and 4); pattern - + - + also needs 2. The minimum is 2.

Constraints

- 1 <= n <= 10^5 - -10^9 <= a[i] <= 10^9, a[i] != 0

Solutions are judged against 2 sample and 9 hidden tests. Sign in to solve it · All problems