チョコレートストア
n 人があるお店の前に並んでいます。このお店はチョコレートだけを販売しています。お客さんが店に入るたびに、お店側は1kg分のチョコレートを仕入れ、そのお客さんがレジへ行く頃には仕入れた1kgをすぐに販売できる状態になります。並んでいる人たちが、それぞれどれだけのチョコレートを必要としているかはわかっています。もしお客さんが入店した時点で店の在庫が足りなければ、そのお客さんは列のいちばん後ろに戻って、改めて順番を待ちます。もし必要な量を買えたら、そのまま店を出て行きます。
ここで求めたいのは、各人が望む量のチョコレートを買うために、何回そのお店へ入ることになるかという回数です。
最初はお店にチョコレートの在庫が一切ありません。
入力
入力の最初の行には、整数
n (1 ≤ n ≤ 10 000) が1つ与えられます。次の行には、
n 個の整数がスペース区切りで与えられ、それぞれ (1 ≤ ≤ 20) として、各人が必要とするチョコレートの量を表します。出力
n 人それぞれが、チョコレートを買うためにお店へ入る回数をスペース区切りで出力してください。Examples
Input | Output |
3
1 3 2 | 1 4 1 |
説明
- 最初の客が入店 → お店に1kgのチョコレートが入荷 ⇒ そのまま1kgを販売し、最初の客は満足して店を出る。
- 次に2番目の客が入店 → お店に1kgのチョコレートが入荷。客が求めるのは3kgなので、足りずに列の最後に戻る。
- 3番目の客が入店 → さらに1kgが入荷（合計2kg） ⇒ 2kgを販売できたので、3番目の客は満足して店を出る。
- その後、2番目の客が再び入店 → お店に1kgが入荷。店の在庫は1kgしかなく、客は3kg欲しいため、また出直す。
- 2番目の客が再度入店 → さらに1kgが入荷。在庫は合計2kgだが、まだ3kgに達しないため、再び出直す。
- 2番目の客がもう一度入店 → 1kgが入荷され、在庫が3kgになる ⇒ ようやく3kgすべてを販売でき、2番目の客は満足して店を出る。
結果として、1番目の客は1回、2番目の客は4回、3番目の客は1回入店しました。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB