Count Sign Changes Between Adjacent Elements (Đếm số lần đổi dấu giữa hai phần tử kề)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$, an adjacent pair $(a_{i-1},a_i)$ for $1\le i<n$ is a sign change exactly when one value is negative and the other is positive:

Equivalently, $a_{i-1}a_i<0$. If either value is zero, the pair is not counted. Count all such adjacent sign changes.

Input

The first line contains $n$. The second line contains $n$ integers $a_i$.

Output

Print the number of adjacent sign changes.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $|a_i|\le10^3$.

Subtask 2 (30 points): $1\le n\le5000$, $|a_i|\le10^6$.

Subtask 3 (50 points): $1\le n\le2\cdot10^5$, $|a_i|\le10^9$.

Example

Input

8
-2 5 0 -3 4 -1 -1 6

Output

4

Explanation

The sample follows the mathematical definition above.