Обратите внимание на нестандартное ограничение по памяти в этой задаче.
С целью отсечения эффективных решений от неэффективных в этой задаче ограничение времени довольно строгое. Предпочтите использование компилируемых статически типизированных языков (например, C++). Если используете Python, то отсылайте решения на PyPy. Постарайтесь написать в самом деле эффективное решение.
Задан массив \(a=[a_1, a_2, \ldots, a_n]\) (\(1 \le a_i \le n\)). Его элемент \(a_i\) называется особым, если существует такая пара индексов \(l\) и \(r\) (\(1 \le l < r \le n\)), что \(a_i = a_l + a_{l+1} + \ldots + a_r\). Иными словами, элемент называется особым, если он представим в виде суммы двух или более подряд идущих элементов массива (не важно, особых или нет).
Выведите количество особых элементов заданного массива \(a\).
Например, если \(n=9\) и \(a=[3,1,4,1,5,9,2,6,5]\), то ответ равен \(5\):
- \(a_3=4\) — особый элемент, так как \(a_3=4=a_1+a_2=3+1\);
- \(a_5=5\) — особый элемент, так как \(a_5=5=a_2+a_3=1+4\);
- \(a_6=9\) — особый элемент, так как \(a_6=9=a_1+a_2+a_3+a_4=3+1+4+1\);
- \(a_8=6\) — особый элемент, так как \(a_8=6=a_2+a_3+a_4=1+4+1\);
- \(a_9=5\) — особый элемент, так как \(a_9=5=a_2+a_3=1+4\).
Обратите внимание, что среди элементов массива \(a\) могут быть равные — если несколько элементов равны и являются особыми, то все они должны быть посчитаны в ответе.