taietura

Fiind dat un șir $V$ format din $N$ numere întregi $V_1, … , V_N$, definim o tăietură în poziția $pos$ ca fiind o subsecvență care conține elementul de pe poziția $pos$. Formal, tăieturile în poziția $pos$ sunt de forma $V_k , V_{k+1}, ... , V_{pos} , ... , V_{r-1}, V_r$ pentru orice $k$, $1 \leq k \leq pos$ și orice $r$, $pos \leq r \leq N$.

Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă.

Definim funcția $\text{MulT}(pos)$ ca fiind numărul de tăieturi în poziția $pos$ care au valoarea $0$.

Cerinţă

Ioana, fiind foarte curioasă din fire, dar și foarte fascinată de această funcție numită $\text{MulT}$, este foarte interesată în a afla rezultatul pentru $\text{MulT}(i)$, unde $1 \leq i \leq N$.

Date de intrare

Fişierul de intrare taietura.in conţine pe prima linie un număr natural $N$, reprezentând numărul de elemente din șirul $V$. Următoarea linie va conține exact $N$ valori întregi despărțite prin câte un spațiu, și anume elementele șirului $V$.

Date de ieșire

Fişierul de ieşire taietura.out va conţine pe prima linie $N$ numere naturale separate prin câte un spațiu, și anume valorile funcției $\text{MulT}(i)$, unde $1 \leq i \leq N$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• Orice element al șirului $V$ este mai mic sau egal în valoare absolută cu $10^9$;
• Pentru teste în valoare de $20$ de puncte $N \leq 100$;
• Pentru teste în valoare de încă $20$ de puncte $N \leq 1 \ 000$.

Exemplul 1

taietura.in

3
0 1 0

taietura.out

1 0 1

Explicație

Rezultatul pentru $\text{MulT}(1)$ este $1$ deoarece există o singură tăietură, și anume $(0)$ care are valoarea $0$. Pentru $\text{MulT}(2)$ rezultatul este $0$ deoarece nu există nicio tăietură aplicată pe poziția $2$ care să aibă valoarea $0$. Rezultatul pentru $\text{MulT}(3)$ este $1$ deoarece există o unică tăietură, și anume $(0)$ care are valoarea $0$.

Exemplul 2

taietura.in

6
2 -2 0 0 1 -1

taietura.out

4 4 6 6 4 4

Explicație

De exemplu, rezultatul pentru $\text{MulT}(2)$ este $4$ deoarece tăieturile formate din subsecvențele $(2, -2)$, $(2, -2, 0)$, $(2, -2, 0, 0)$, $(2, -2, 0, 0, 1, -1)$ au valoarea $0$.