题目描述

在和 Sakurako 一起旅行后，Kousuke 非常害怕，因为他忘记了他的编程作业。在这次作业中，老师给了他一个包含 $n$ 个整数的数组 $a$，并要求他计算数组 $a$ 中不重叠线段的数量，使得每个线段都被认为是美丽的。

如果线段 $[l, r]$ 满足 $a_l + a_{l+1} + ... + a_{r-1} + a_r = 0$，则该线段被认为是美丽的。

对于固定数组 $a$，您的任务是计算不重叠的美丽线段的最大数量。

格式要求

输入格式

输入共两行。

第一行包含一个整数 $n$，代表数组的长度$(1 \leq n \leq 10^5)$。

第二行包含 $n$ 个整数 $a_i$，代表数组中的元素$(-10^5 \leq a_i \leq 10^5$，且 $-10^5 \leq a_1 + a_2 + ... a_n \leq 10^5)$。

输出格式

输出一个整数：不重叠的美丽线段的最大数量。

样例

6
0 -4 0 3 0 1

3

提示

三个 $0$ 可以算做 $3$ 个不重叠的美丽线段。