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)$.