Rezolvare PBinfo #3499

Se dă un șir \(A\) format din \(n\) elemente din mulțimea \(\{0, 1\}\). Numim secvență a șirului \(A\) orice succesiune de elemente situate pe poziții consecutive în șir.

Cerința

Să se determine numărul de secvențe ale șirului \(A\) ce conțin de două ori mai mulți de \(1\) decât de \(0\).

Date de intrare

Pe prima linie a fișierului secv011.in se află numărul \(n\). Pe următoarea linie se află cele \(n\) elemente ale șirului \(A\), separate prin câte un spațiu.

Date de ieșire

Fișierul secv011.out va conține pe prima linie numărul cerut.

Restricții și precizări

• Pentru teste în valoare de 20 de puncte, \(1 \le n \le 1.000\).
• Pentru teste în valoare de 50 de puncte, \(1 \le n \le 5.000\).
• Pentru teste în valoare de 100 de puncte, \(1 \le n \le 1.000.000\).

Exemplu:

secv011.in

6
1 0 1 1 1 0

secv011.out

4

Explicație

Secvențele cu proprietatea dată sunt \((1, 0, 1)\), \((0, 1, 1)\), \((1, 1, 0)\) și \((1, 0, 1, 1, 1, 0)\).