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

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên $a_0,a_1,\ldots,a_{n-1}$. Với mỗi $i$ thỏa $1\le i<n$, cặp kề $(a_{i-1},a_i)$ được gọi là đổi dấu khi một số âm và số còn lại dương, tức

Tương đương, cặp đổi dấu khi

Nếu một trong hai phần tử bằng $0$, cặp đó không được tính là đổi dấu. Hãy đếm số chỉ số $i$ tạo thành một cặp đổi dấu.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In một số nguyên: số cặp kề đổi dấu.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $|a_i|\le10^3$.

Subtask 2 (30 điểm): $1\le n\le5000$, $|a_i|\le10^6$.

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

Ví dụ

Input

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

Output

4

Giải thích

Các cặp đổi dấu là $(-2,5)$, $(-3,4)$, $(4,-1)$ và $(-1,6)$. Hai cặp chứa $0$ không được tính.