Обратите внимание на нестандартное ограничение по памяти в этой задаче.

С целью отсечения эффективных решений от неэффективных в этой задаче ограничение времени довольно строгое. Предпочтите использование компилируемых статически типизированных языков (например, 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$$$ могут быть равные — если несколько элементов равны и являются особыми, то все они должны быть посчитаны в ответе.