D. Ненулевые отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Коли есть массив целых чисел $$$a_1, a_2, \dots, a_n$$$. Числа в массиве могут быть и положительными, и отрицательными, но так как Коля не любит число $$$0$$$, то таких чисел в его массиве нет.

Коле не нравится, что сумма элементов на некоторых подотрезках его массива может быть равна $$$0$$$. Под подотрезком массива следует понимать некоторую непустую последовательность подряд идущих элементов массива.

Вы должны помочь Коле и сделать так, чтобы в его массиве не было подотрезков с суммой элементов равной $$$0$$$. Для этого вы можете вставлять в его массив произвольные целые числа между любыми соседними элементами массива (числа могут быть любые: положительные, отрицательные, $$$0$$$, любые по абсолютной величине, даже не представимые в стандартных типах данных во многих языках программирования).

Определите минимальное количество произвольных целых чисел, которые нужно добавить в массив Коли таким образом, чтобы после этого в массиве не было подотрезков с суммой элементов равной $$$0$$$.

Входные данные

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество элементов в массиве Коли.

Во второй строке следует $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}, a_i \neq 0$$$) — описание массива Коли.

Выходные данные

Выведите минимальное количество произвольных целых чисел, которые нужно добавить в массив Коли таким образом, чтобы после этого в массиве не было подотрезков с суммой элементов равной $$$0$$$.

Примеры
Входные данные
4
1 -5 3 2
Выходные данные
1
Входные данные
5
4 -2 3 -9 2
Выходные данные
0
Входные данные
9
-1 1 -1 1 -1 1 1 -1 -1
Выходные данные
6
Входные данные
8
16 -5 -11 -15 10 5 4 -4
Выходные данные
3
Примечание

В первом примере есть один подотрезок, сумма элементов которого равна $$$0$$$. Он начинается со второго элемента и заканчивается в четвертом элементе. Достаточно добавить один элемент, чтобы в массиве не было подотрезков с суммой элементов равной нулю. Например, можно добавить число $$$1$$$ между вторым и третьим элементами массива.

Во втором примере изначально нет подотрезков с суммой элементов равной $$$0$$$, поэтому никаких чисел в массив добавлять не нужно.