Algoritmi e Strutture Dati

Il Negozio di Cioccolato

Ci sono n persone in attesa davanti a un negozio che vende esclusivamente cioccolato. Ogni volta che un cliente entra, il negozio riceve 1kg di cioccolato e, non appena il cliente si reca alla cassa, può già vendere quel chilogrammo appena arrivato.
Conosciamo la quantità di cioccolato desiderata da ognuna delle persone in fila. Se una persona entra ma in negozio non c’è abbastanza cioccolato per soddisfare la sua richiesta, quella persona torna in fondo alla coda e attende il proprio turno per rientrare. Quando invece una persona riesce ad acquistare tutto il cioccolato che le serve, esce subito dal negozio definitivamente.
L’obiettivo è determinare quante volte ciascuna persona entrerà nel negozio prima di ottenere tutto il cioccolato che desidera.
All’inizio, il negozio non ha alcuna scorta di cioccolato.

Input

La prima riga dell’input contiene un solo intero n (1 ≤ n ≤ 10 000).
La riga successiva contiene n interi separati da spazio, che rappresentano le quantità di cioccolato richieste (1 ≤ ≤ 20).

Output

Il programma deve stampare n numeri separati da spazio, dove ciascun numero indica quante volte la persona corrispondente è entrata in negozio prima di acquistare tutto il cioccolato di cui aveva bisogno.

Examples

Input
Output
3 1 3 2
1 4 1

Explanation

  1. Il primo cliente entra → il negozio riceve 1kg di cioccolato ⇒ può venderlo subito al primo cliente, che quindi esce soddisfatto.
  1. Poi entra il secondo cliente → il negozio riceve 1kg di cioccolato. Il cliente però ne vuole 3, quindi torna in fondo alla fila.
  1. Entra il terzo cliente → il negozio riceve 1kg di cioccolato (ora ce ne sono 2 in totale) ⇒ può venderli al terzo cliente, che così lascia il negozio soddisfatto.
  1. Il secondo cliente torna → il negozio riceve 1kg di cioccolato. In tutto ce n’è soltanto 1kg, ma al cliente ne servono 3, quindi deve uscire di nuovo.
  1. Il secondo cliente rientra ancora → il negozio riceve 1kg di cioccolato. In totale ora ci sono 2kg, ma gliene servono 3, quindi esce di nuovo.
  1. Il secondo cliente entra un’altra volta → il negozio riceve 1kg di cioccolato (salendo a 3kg complessivi) ⇒ può finalmente acquistare i 3kg che gli servono ed esce soddisfatto.
Così, il primo cliente è entrato soltanto 1 volta, il secondo 4 volte e il terzo 1 volta.

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue