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 ai 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 dinaintea 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ța

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 celă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 a1, …, aN, 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 ≤ N ≤ 200.000
• 1 ≤ ai ≤ 400.000
• a1 + ... + aN ≤ 400.000
• Pentru 12 puncte, N ≤ 12
• Pentru alte 12 puncte, 1 ≤ N ≤ 100 și a1 = ... = aN = 1
• Pentru alte 20 puncte, 1 ≤ N ≤ 100
• Pentru alte 28 puncte, 1 ≤ N ≤ 1000 și a1 + ... + aN ≤ 2000
• Pentru alte 28 puncte, fără alte restricții

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]