Красота массива \(v_1,v_2,\ldots,v_n\) равняется количеству индексов \(i\) (\(1 \le i \le n\)), таких что \(v_1+v_2+\ldots+v_i = 0\).
У вас есть массив \(a_1,a_2,\ldots,a_n\) длины \(n\). Вы можете применить к нему следующую операцию сколько угодно раз:
- выбрать индекс \(i\) (\(1 \le i \le n\)), такой что \(a_i=0\);
- после этого заменить \(a_i\) на произвольное целое число.
Какой максимальной красоты массив \(a\) вы можете получить?
Выходные данные
Для каждого набора входных данных выведите одно число: максимальную красоту массива \(a\) после применения к нему операций.
Примечание
В первом наборе входных данных вы можете заменить \(a_2\) на \(-2\) за одну операцию. После этого массив \(a\) станет равен \([2,-2,1,-1,0]\) и будет иметь красоту \(3\):
- \(a_1+a_2=2-2=0\);
- \(a_1+a_2+a_3+a_4=2-2+1-1=0\);
- \(a_1+a_2+a_3+a_4+a_5=2-2+1-1+0=0\).
Во втором наборе входных данных вы можете заменить \(a_3\) на \(-2\,000\,000\,000\), чтобы получить массив красоты \(1\).
В третьем наборе входных данных вы можете не делать операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
8
3 0 2 -10 10 -30 30 0
9
1 0 0 1 -1 0 1 0 -1
|
3
1
4
4
5
|