Tổng 0

Quân có một dãy số nguyên \(a_{1}, a_{2}, ..., a_{n}\). Dãy có thể có số âm hoặc số dương, nhưng Quân không thích số \(0\).

Quân cực kì ghét những dãy con liên tiếp có tổng bằng \(0\). Bạn cần giúp Quân chèn thêm vài số vào trong dãy, sao cho sau khi chèn, không tồn tại dãy con liên tiếp có tổng bằng \(0\). Bạn chỉ có thể chèn số vào giữa hai phần tử kề nhau trong dãy số. Và trong những cách chèn số, chọn ra cách có số lượng số chèn vào là ít nhất.

Input

Dòng đầu tiên gồm một số nguyên dương \(n\) - số lượng phần tử của dãy.

Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, ..., a_{n}\) \((-10^9 <= a_{i} <= 10^9, a_{i} \neq 0)\).

Output

Một số nguyên không âm duy nhất là kết quả bài toán

Example

4
1 -5 3 2

1

5
4 -2 3 -9 2

0

9
-1 1 -1 1 -1 1 1 -1 -1

6

Scoring

Có \(40\%\) \(n <= 20\).

\(60\%\) còn lại \(n <= 200000\).