Olympiad Pizza

Interview

Time limit2sMemory limit512 MB

Summary

Contestants queue for pizza slices; each takes one slice per turn and rejoins the back if still hungry. Report the second each finishes.

Level: Medium4 of 10
Topics: Queue, Simulation, Implementation, Array
Solved: No attempts yet

Problem

At the Olympiad finals we serve pizza to the contestants. When the pizza arrives the contestants line up, and each one receives a single slice when his or her turn comes. A contestant who is not full after that slice goes back to the end of the line and waits for the next turn.

You are given the number of slices each contestant needs to be full. Compute how long it takes to feed everyone. One slice is handed out every second, and a contestant who is full never returns to the line.

Input

The first line contains the number of contestants $N$ . ( $1 \le N \le 1000$ )

The second line contains $N$ integers separated by spaces, the number of slices each contestant needs, in line order. Each value is between $1$ and $100$ .

Output

Print one line with $N$ integers separated by spaces, the second at which each contestant receives all the slices he or she needs, in line order.

Hint

With 4 contestants needing 1, 3, 1, 4 slices, the contestants who receive a slice are, in order: 1, 2, 3, 4, 2, 4, 2, 4, 4. At second 1 contestant 1 is full, at second 3 contestant 3 is full, at second 7 contestant 2 finishes, and at second 9 contestant 4 takes the last slice.

Examples3

Example 1
Input
```
4
1 3 1 4
```
Expected output
```
1 7 3 9
```
Example 2
Input
```
5
1 1 1 1 1
```
Expected output
```
1 2 3 4 5
```
Example 3
Input
```
2
2 2
```
Expected output
```
3 4
```