Tort

Alexandra, prințesa Regatului Visurilor a primit un tort și vrea să îl împartă cu prietenii ei. Astfel ea va organiza o petrecere unde îi va invita. Tortul Alexandrei este format din $N$ bucăți, iar a $i$-a bucată are $a_i$ cireșe. Alexandra va împărți tortul în mai multe secvențe continue de bucăți, astfel încât fiecare bucată este inclusă în exact o secvență, și fiecare secvență conține cel puțin o bucată de tort. Prima secvență – cea care conține prima bucată – o va mânca în noaptea de înaintea petrecerii, iar restul bucăților le va da celorlalți prieteni invitați. Pentru a nu îi supăra, Alexandra vrea ca fiecare secvență dată unui prieten să conțină la fel de multe cireșe ca oricare altă secvență dată unui prieten (dar nu neapărat la fel de multe cireșe ca aceea mâncată de ea înaintea petrecerii). Alexandra trebuie să invite cel puțin un prieten la petrecere.

Cerință

Dându-se $N$ și șirul $a$, să se afle numărul de moduri în care Alexandra ar putea să împartă tortul în secvențe continue, astfel încât să se respecte condițiile din enunț. Două moduri de a împărți tortul se consideră a fi distincte dacă și numai dacă există în unul o secvență care nu există în ceălalt (dacă am reprezenta un mod de împărțire în secvențe prin intermediul șirului crescător al indicilor de început pentru fiecare secvență din acea împărțire, două moduri de împărțire sunt distincte dacă șirurile de indici asociate lor sunt diferite).

Formal, dându-se un șir de numere, se vrea să aflăm numărul de moduri de a împărți șirul în cel puțin două subsecvențe, astfel încât sumele elementelor tuturor subsecvențelor să fie egale, prima putând să aibă suma elementelor diferită de a celorlalte.

Date de intrare

Prima linie a fișierului de intrare tort.in conține numărul $N$. A doua linie conține valorile $a_1, \dots , a_N$, separate prin spații.

Date de ieșire

Singura linie a fișierului de ieșire tort.out va conține numărul cerut.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq a_1, \dots ,a_n \leq 400 \ 000$
• $a_1 + \dots + a_n \leq 400 \ 000$

Exemplu

tort.in

5
1 1 2 1 1

tort.out

6

Explicație

Împărțirile valide sunt:

1. $[1], [1, 2, 1, 1]$
2. $[1, 1], [2, 1, 1]$
3. $[1, 1], [2], [1, 1]$
4. $[1, 1, 2], [1, 1]$
5. $[1, 1, 2], [1], [1]$
6. $[1, 1, 2, 1], [1]$