Đếm số lần đổi dấu (Count Sign Changes)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given an integer sequence $a_1,a_2,\ldots,a_n$.

For each $i$ with $1\le i<n$, the adjacent pair $(a_i,a_{i+1})$ is a sign change exactly when one value is negative and the other is positive:

If $a_i=0$ or $a_{i+1}=0$, that pair is not counted as a sign change.

Count the indices $i$ satisfying the condition.

Input

The first line contains integer $n$. The second line contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$.

Output

Print one integer: the number of sign changes between adjacent elements.

Subtasks

Subtask 1 (100 points): $1\le n\le 2\cdot 10^5$; $|a_i|\le 10^9$.

Example

Input

6
-3 2 0 -5 4 -1

Output

3

Explanation

The pairs $(-3,2)$, $(-5,4)$, and $(4,-1)$ change sign. Pairs containing $0$ are not counted.