Codeforces Round 632 (Div. 2) |
---|
Закончено |
Евгений любит работать с массивами. Сегодня ему нужна ваша помощь, чтобы решить одну сложную задачку.
Массив $$$c$$$ является подмассивом $$$b$$$, если $$$c$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Назовем непустой массив хорошим, если для любого непустого подмассива этого массива, сумма его элементов не равна нулю. К примеру, массив $$$[-1, 2, -3]$$$ является хорошим, так как все массивы $$$[-1]$$$, $$$[-1, 2]$$$, $$$[-1, 2, -3]$$$, $$$[2]$$$, $$$[2, -3]$$$, $$$[-3]$$$ имеют ненулевую сумму элементов. В то же время, массив $$$[-1, 2, -1, -3]$$$ не является хорошим, так как его подмассив $$$[-1, 2, -1]$$$ имеет сумму элементов равную $$$0$$$.
Помогите Евгению посчитать количество непустых хороших подмассивов данного массива $$$a$$$.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$) — длину массива $$$a$$$.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.
Выведите одно целое число — количество хороших подмассивов $$$a$$$.
3 1 2 -3
5
3 41 -41 41
3
В первом примере следующие подмассивы являются хорошими: $$$[1]$$$, $$$[1, 2]$$$, $$$[2]$$$, $$$[2, -3]$$$, $$$[-3]$$$, Однако подмассив $$$[1, 2, -3]$$$ не является хорошим, поскольку его подмассив $$$[1, 2, -3]$$$ имеет сумму элементов, равную $$$0$$$.
Во втором примере все три подмассива размера 1 хорошие и только они. В то же время, подмассив $$$[41, -41, 41]$$$ не является хорошим, поскольку его подмассив $$$[41, -41]$$$ имеет сумму элементов, равную $$$0$$$.
Название |
---|