== include(page="template/taskheader" task_id="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 ≤ k ≤ pos şi orice r, pos ≤ r ≤ N. Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă. Definim funcţia MulT(pos) ca fiind numărul de tăieturi în poziţia pos care au valoarea 0.

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 ≤ k ≤ pos$ şi orice $r, pos ≤ r ≤ N$. Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă. Definim funcţia $MulT(pos)$ ca fiind numărul de tăieturi în poziţia pos care au valoarea $0$.

h2. Cerinţă

Ioana, fiind foarte curioasă din fire, dar şi foarte fascinată de această funcţie numită MulT, este foarte interesată în a afla rezultatul pentru MulT (i), unde 1 ≤ i ≤ N.

Ioana, fiind foarte curioasă din fire, dar şi foarte fascinată de această funcţie numită $MulT$, este foarte interesată în a afla rezultatul pentru $MulT (i)$, unde $1 ≤ i ≤ N$.

h2. 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.

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

h2. 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 MulT (i), unde 1 ≤ i ≤ N.

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 $MulT (i)$, unde $1 ≤ i ≤ N$.

h2. Restricţii
* $1 ≤ N ≤ 100 000$

* $Orice element al şirului V este mai mic sau egal în valoare absolută cu 109.$

* $Orice element al şirului V este mai mic sau egal în valoare absolută cu 1.000.000.000$

* $Pentru teste în valoare de 20 de puncte N ≤ 100$
* $Pentru teste în valoare de încă 20 de puncte N ≤ 1000$