G. Global warming
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Global warming is causing massive ice melting in Antarctica, leading to coastal cities being submerged. In Bolivia, as a landlocked country, we are not as concerned about this, as no city is directly affected. For example, Cochabamba is at 2558 meters above sea level, La Paz at 3625 meters, and even Santa Cruz, at 416 meters, is safe. To the west, we have the Andes mountain range with its high peaks, such as Illimani, which rises to 6462 meters. To the east lies the vast Amazon region and Brazil, where nearly 40

Unfortunately, global warming has reached an irreversible point. It is known that starting next year, the sea level will rise 1 meter each year until it reaches $$$10^9$$$ meters. We are all doomed due to our excessive use of plastic soda bottles, pizza boxes, egg cartons, and for leaving the light on all night thinking that our parents would turn it off. Now we want to know how many years each segment of the map has left before being flooded, imagining that the water comes from both the Pacific Ocean (west) and the Atlantic Ocean (east).

To simplify, we will consider Bolivia and the neighboring countries as one-dimensional. A height map will be provided from one coast to the other. It is well known that a straight line between the Atlantic and the Pacific, passing through Cochabamba, is 2880 km long, so that is the limit. Calculate how many years each segment has left before being flooded, assuming that the ocean water is infinite and that once a segment is flooded, its level does not decrease.

Input

The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2880$$$) representing the number of segments. The first and last segments will always have a height of 0 meters. The second line contains $$$n$$$ integers $$$h_i$$$ ($$$0 \leq h_i \leq 6542$$$) representing the height of each segment in meters.

Output

Print $$$n$$$ numbers, where each number indicates how many years each segment has left before it gets flooded.

Examples
Input
5
0 1 0 2 0
Output
1 2 2 3 1 
Input
16
0 100 1000 3625 6462 4000 2880 2558 1500 416 200 400 100 900 288 0
Output
1 101 1001 3626 6463 4001 2881 2559 1501 901 901 901 901 901 289 1 
Input
3
0 10 0
Output
1 11 1