Алекс считает, что некоторый массив является хорошим, если существует элемент, который является суммой всех других элементов (сумма всех других элементов равна \(0\), если других элементов нет). Например, массив \([1,6,3,2]\) является хорошим, так как \(1+3+2=6\). Кроме того, массив \([0]\) также является хорошим. Однако массивы \([1,2,3,4]\) и \([1]\) не являются хорошими.
У Алекса есть массив \(a_1,a_2,\ldots,a_n\). Помогите ему посчитать количество хороших непустых префиксов массива \(a\). Другими словами, посчитайте количество целых чисел \(i\) (\(1 \le i \le n\)), для которых префикс длины \(i\) (т.е. \(a_1,a_2,\ldots,a_i\)) является хорошим.
Примечание
В четвертом примере массив имеет пять префиксов:
- префикс \([0]\) является хорошим массивом, как упоминается в условии;
- префикс \([0, 1]\) не является хорошим массивом, так как \(0 \ne 1\);
- префикс \([0, 1, 2]\) не является хорошим массивом, так как \(0 \ne 1 + 2\), \(1 \ne 0 + 2\) и \(2 \ne 0 + 1\);
- префикс \([0, 1, 2, 1]\) является хорошим массивом, так как \(2 = 0 + 1 + 1\);
- префикс \([0, 1, 2, 1, 4]\) является хорошим массивом, так как \(4 = 0 + 1 + 2 + 1\).
Как видно, три из них являются хорошими, поэтому ответ равен \(3\).