Бизнесмен Василий готовится к уплате налогов за квартал ($$$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]$$$, потому что все части должны быть непустыми.
В третьем примере выполнить подходящее разбиение невозможно.
