Problem Description

The 'tapisu' of a sequence is defined as the number of consecutive subsequences of length $1$ or more whose elements sum to $0$. Even if the contents of the subsequences are the same, they are counted as different if their positions differ.

You are given a sequence of length $N$, $A_1, A_2, ..., A_N$. You can change one element of this sequence to any integer value. Find the minimum 'tapisu' of the sequence.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

Output Format

Output the answer in one line.

Sample Input and Output

Sample Input #1

4
0 0 0 0

Sample Output #1

4

Sample Input #2

6
1 -1 -1 2 -2 0

Sample Output #2

2

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $|A_i| \leq 10^9$
• All inputs are integers

Partial Points

• If you solve the dataset where $N \leq 5000$, you will be awarded $ 40 $ points.

Sample Explanation 1

For example, if you change $ A_2 $ to $ 1 $, the subsequences whose sum is $ 0 $ are $ [1,1] $, $ [3,3] $, $ [4,4] $, $ [3,4] $, which totals to $ 4 $ and is the minimum.

见题面 Input 部分

见题面 Output 部分