Županijsko NATJECANJE 2015. / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

U Mirkovom akvariju nalazi se N riba mesožderki. Mirko zna koliko je koja riba velika, a njihove veličine su prirodni brojevi.

Riba može progutati bilo koju drugu ribu koja je u tom trenutku strogo manja od nje.

Međutim, nakon što riba proguta drugu ribu, njena se veličina uveća za trenutnu veličinu pojedene ribe.

Npr. ako riba veličine 5 pojede ribu veličine 3, onda će njezina nova veličina biti 8.

Svaka riba progutat će najviše jednu drugu ribu (koja je možda već prije progutala neku manju, koja je također možda progutala manju ribu itd).

Napišite program koji će na temelju početnih veličina riba, za svaku ribu odrediti koliko najviše može u svom trbuhu odjednom imati drugih riba.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj N (N ≤ 200 000), broj Mirkovih riba.

Sljedeći redak sadrži N prirodnih brojeva RK (1 ≤ RK ≤ 1 000 000 000) odvojenih sa po jednim razmakom – veličine Mirkovih riba.

Veličine riba bit će poredane od manjih prema većima.

Izlazni podaci

Potrebno je ispisati N redova. U K-tom redu potrebno je ispisati koliko najviše riba može K-ta riba odjednom imati u trbuhu.

Primjeri test​ podataka

Ulaz

5
1 2 5 7 9

Izlaz

0
1
2
2
3

Objašnjenje

Ulaz

5
1 2 4 8 16

Izlaz

0
1
2
3
4