Algoritmos e Estruturas de Dados

A Loja de Chocolate

Há n pessoas à porta de uma loja. A loja vende apenas chocolates. Sempre que um cliente entra na loja de chocolates, a loja recebe 1 kg de chocolate. Quando o cliente chega ao balcão, a loja já pode vender esse 1 kg.
Sabemos a quantidade de chocolate que cada pessoa na fila deseja. Se alguém entrar na loja e não houver chocolate suficiente, essa pessoa vai para o fim da fila e espera para tentar novamente. Se conseguir comprar o chocolate, recebe o que precisa e sai da loja.
É pedido que se determine quantas vezes cada pessoa entra na loja até obter a quantidade de chocolate desejada.
Inicialmente, a loja não tem qualquer chocolate.

Input

A primeira linha do input contém um único inteiro n (1 ≤ n ≤ 10 000).
A linha seguinte contém n inteiros separados por espaço, representando a quantidade de chocolate que cada pessoa precisa (1 ≤ ≤ 20).

Output

O programa deve imprimir n inteiros separados por espaço, representando o número de vezes que cada pessoa entra na loja.

Exemplos

Input
Output
3 1 3 2
1 4 1

Explicação

  1. O primeiro cliente entra na loja → a loja recebe 1 kg de chocolate ⇒ vende 1 kg ao primeiro cliente, que sai satisfeito.
  1. Em seguida, o segundo cliente entra → a loja recebe 1 kg de chocolate. No entanto, o cliente quer 3 kg, por isso volta para o fim da fila.
  1. O terceiro cliente entra na loja → a loja recebe mais 1 kg de chocolate (total de 2 kg) ⇒ vende 2 kg ao terceiro cliente, que sai satisfeito.
  1. Depois, o segundo cliente entra novamente → a loja recebe 1 kg de chocolate. Desta vez, a loja só tem 1 kg, mas o cliente precisa de 3, então sai para o fim da fila outra vez.
  1. O segundo cliente volta a entrar → a loja recebe 1 kg de chocolate. Agora a loja soma 2 kg, mas o cliente quer 3, então volta a sair.
  1. O segundo cliente entra mais uma vez → a loja recebe 1 kg de chocolate (3 kg no total) ⇒ vende 3 kg ao cliente, que sai satisfeito.
Assim, o primeiro cliente entrou na loja apenas 1 vez, o segundo entrou 4 vezes e o terceiro entrou 1 vez.

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