Statement is not available in English language
5. Бизнесмен Василий
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бизнесмен Василий готовится к уплате налогов за квартал ($$$3$$$ месяца). Действующая налоговая система в государстве, в котором Василий ведет свой бизнес, устроена таким образом, что величина налога зависит от прибыли в конце каждого месяца. Чистая прибыль бизнесмена определяется как разница между доходом и расходом. Разумеется, если бизнес идет не очень удачно, прибыль бизнесмена может быть отрицательной — в этом случае речь идет об убытке.

Все доходы и расходы Василий записывал в журнал в виде целых чисел. Теперь Василий должен подать налоговую декларацию с суммой доходов на конец каждого месяца, другими словами ему необходимо поделить последовательность записей в журнале на три непустые части.

При этом Василий хочет сделать это таким образом, чтобы прибыль в каждой части была одинаковой (возможно даже отрицательной) — в этом случае сумма налога будет минимальной. Менять записи в журнале местами нельзя.

По имеющимся данным определите количество способов выполнить такое разбиение.

Входные данные

В первой строке входных данных содержится единственное натуральное число $$$N$$$ – количество записей в журнале Василия $$$(3 \leq N \leq 10^5)$$$.

В следующих $$$N$$$ строках записаны целые числа $$$a_i$$$, соответствующие записям в журнале $$$(-10^8 \leq a_i \leq 10^8)$$$.

Выходные данные

Выведите единственное целое число - количество способов выполнить необходимое разбиение

Система оценки

Решение, верно работающие при $$$n \leq 200$$$, будет оцениваться в 40 баллов.

Решение, верно работающие при $$$n \leq 1000$$$, будет оцениваться в 60 баллов.

Примеры
Входные данные
6
4
3
-3
5
-1
4
Выходные данные
2
Входные данные
3
0
0
0
Выходные данные
1
Входные данные
4
3
-2
3
1
Выходные данные
0
Примечание

В первом примере в журнале записано $$$6$$$ чисел $$$[4, 3, -3, 5, -1, 4]$$$ из них можно получить два разбиения: $$$[4], [3, -3, 5, -1], [4]$$$ и $$$[4, 3, -3], [5, -1], [4]$$$.

Во втором примере в журнале записаны три нуля — имеется единственное возможное разбиение $$$[0], [0], [0]$$$, потому что все части должны быть непустыми.

В третьем примере выполнить подходящее разбиение невозможно.