Шоколадный магазин
Впереди магазина стоит
n человек. Этот магазин продаёт только шоколад. Каждый раз, когда клиент заходит в шоколадный магазин, в нём появляется 1 кг шоколада. К моменту, когда покупатель подходит к кассе, этот килограмм уже можно продать.Мы знаем, сколько шоколада хочет каждый из находящихся в очереди людей. Если человек зашёл в магазин и шоколада не хватает, он становится в конец очереди и ждёт повторного входа. Если же шоколада достаточно, человек покупает нужное количество и уходит из магазина.
Вам нужно определить, сколько раз каждый человек зайдёт в магазин, чтобы купить желаемое количество шоколада.
Сначала в магазине нет шоколада.
Входные данные
В первой строке входных данных дано одно целое число
n (1 ≤ n ≤ 10 000).В следующей строке записаны
n целых чисел, разделённых пробелами, которые показывают, сколько шоколада нужно каждому человеку (1 ≤ ≤ 20).Выходные данные
Программа должна вывести
n целых чисел, разделённых пробелами, обозначающих, сколько раз каждый человек зашёл в магазин.Примеры
Input | Output |
3
1 3 2 | 1 4 1 |
Пояснение
- Первый покупатель заходит в магазин → магазин получает 1 кг шоколада ⇒ сразу продаёт 1 кг первому покупателю, и он уходит довольным.
- Затем подходит второй покупатель → магазин снова получает 1 кг шоколада. Однако покупателю нужно 3 кг, поэтому он возвращается в конец очереди.
- Третий покупатель заходит в магазин → магазин получает ещё 1 кг шоколада (итого 2 кг) ⇒ продаёт 2 кг этому покупателю, и он уходит.
- Затем второй покупатель снова заходит в магазин → магазин получает 1 кг шоколада. Всего 1 кг, а покупателю нужно 3, поэтому он выходит из магазина.
- Второй покупатель снова заходит → магазин получает 1 кг шоколада. Теперь всего 2 кг, а нужно 3, поэтому он опять уходит.
- Второй покупатель заходит в магазин ещё раз → магазин получает 1 кг шоколада (итого 3 кг) ⇒ продаёт 3 кг покупателю, после чего он уходит удовлетворённым.
Таким образом, первый покупатель заходил в магазин 1 раз, второй — 4 раза, а третий — 1 раз.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB