После поездки с Сакурако Косукэ очень испугался, потому что забыл о своем задании по программированию. В этом задании учитель дал ему массив \(a\) из \(n\) целых чисел и попросил вычислить количество непересекающихся отрезков массива \(a\), таких что каждый отрезок считается красивым.
Отрезок \([l,r]\) считается красивым, если \(a_l + a_{l+1} + \dots + a_{r-1} + a_r=0\).
Для фиксированного массива \(a\) ваша задача состоит в том, чтобы вычислить максимальное количество непересекающихся красивых сегментов.
Выходные данные
Для каждого теста выведите одно целое число: максимальное количество непересекающихся красивых отрезков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1
|
1
2
3
|