Problem G
Server Space

Image by Victor Grigas, commons.wikimedia.org

Some restructuring is required in the computer room and unfortunately it falls to you to take care of it. As cloudy as it seems to always be in the city of terror, you would think it would be easy to fit some of these servers in the clouds, but management always says it is too expensive when you bring the idea up.

Well, then there is nothing left but to get to it. Digging up the diagrams of how all the server closets are organised you see where they are all affixed to the wall. They all stand along one wall, reaching from the floor and most of the way up to the ceiling. The leftmost server closet is placed against the left wall and the closets do not have any gaps between them.

You want to spend as little time as possible in the computer room, because the air is stale and the lights dim in there. Unfortunately the diagram only shows you where the server closets are affixed to the wall, which is on the middle of the closet. You however need to know how wide they are. Can you calculate the widths from this?

Input

The first line of input contains one integer $1 \leq N \leq 10^5$, the number of closets. The next $N$ lines each contain an integer $1 \leq x \leq 10^9$, a point where a closet is affixed to the wall.

Output

Print $N$ lines, each containing the width of a closet. Print the widths in the order that the closets are affixed to the wall from left to right. You may assume there is a valid solution where all widths are strictly positive.

Explanation of samples

Figure 1: Possible layout of sample 1

4
12
7
18
3

6
2
8
4