Se da un sir a_1, a_2, ..., a_n de numere naturale nenule. Numim suma de prefix de lungime k valoarea a_1 + a_2 + ... + a_k.
Pentru fiecare element a_i al sirului, determinati lungimea k a sumei de prefix egale cu a_i, sau 0 daca nicio suma de prefix nu este egala cu a_i.
- Date de intrare
- Pe prima linie se afla n, iar pe a doua linie cele n numere ale sirului.
- Date de iesire
- Se afiseaza pe o singura linie n numere separate prin cate un spatiu: al i-lea numar este lungimea k a sumei de prefix egale cu a_i, sau 0 daca nu exista.
- Restrictii
- 2 <= n <= 200 000 1 <= a_i <= 2 000 000 000
Exemple
Exemplul 1
Intrare
6 2 3 5 1 11 10
Iesire
1 0 2 0 4 3
Exemplul 2
Intrare
4 1 1 2 4
Iesire
1 1 2 3