The Chocolate Store
There are
n people standing in front of a store. The store sells only chocolates. Every time a client enters the chocolate store, the store receives 1kg of chocolate. By the time the client approaches the cashier, they can already sell that 1kg.We know how much chocolate each of the people in the line wants. If a person enters the store and there isn’t enough chocolate, they get to the very end of the line and wait to get inside again. If they buy the chocolate, they get it and leave the store.
You are asked to find the number of times each person will enter the shop to buy the desired amount of chocolate.
Initially, the store has no chocolate.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 10 000).The next line contains
n space-separated integers representing the amount of chocolate each person needs Output
The program should print
n space-separated integers representing the number of times each person will enter the shop.Examples
Input | Output |
3
1 3 2 | 1 4 1 |
Explanation
- The first customer enters the store → the store gets 1kg of chocolate ⇒ they can sell 1kg to the first customer, so the customer leaves satisfied.
- Then the second customer approaches → the store gets 1kg of chocolate. Yet, the customer wants 3kg, so he gets back to the end of the queue.
- The third customer enters the store → the store gets another 1kg of chocolate (2kg in total) ⇒ they can sell 2kg to the customer, so the customer leaves satisfied.
- Then the second customer enters again → the store gets 1kg of chocolate. The store only has 1kg, while the customer wants 3. So, the customer gets out of the store.
- The second customer enters the store again → the store gets 1kg of chocolate. The store only has 2kg now, while the customer wants 3kg. So, the customer gets out again.
- The second customer enters the store again → the store gets 1kg of chocolate (3kg in total) ⇒ they sell 3kg to the customer and the customer leaves satisfied.
So, the first customer entered the store only 1 time. The second customer entered the store 4 times, while the third one entered the store once.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB