Adjacent Sign Changes

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Count adjacent pairs of opposite nonzero signs; zero breaks the run. Avoid multiplying two 32-bit values.

Input

0<=n<=100000 followed by signed 32-bit integers.

Output

The number of adjacent opposite-sign pairs.

Subtasks

• Subtask 1 (20%): n<=6, |ai|<=10.
• Subtask 2 (30%): n<=100, |ai|<=10000.
• Subtask 3 (50%): n<=100000, ai thuộc int 32 bit.

Examples

Example 1

Input

5
-2 3 0 -1 4

Output

2

Explanation

The pairs (-2,3) and (-1,4) count; zero breaks adjacency.

Example 2

Input

2
-2147483648 2147483647

Output

1

Explanation

Compare signs directly without overflow.