B. Spring cleaning
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Valley of the Moomins, there are several houses in a row, in which the Moomin family and their friends live. Each house has its own height. Spring is approaching, and all the residents have decided to carry out a large general cleaning, which also includes cleaning the roof.

The only problem is that every resident will need a ladder to get to their roof. They can use a ladder to climb from the ground to the roof of any of the houses whose height does not exceed the length of the ladder. Once on the roof, they can move to the next roof on the left or right, provided that the height of this neighboring roof differs from the height of the roof on which they are located, no more than the length of the ladder they took. You can make several transitions to the neighboring roof, if the length of the stairs is enough for this.

Help each of the residents to determine the minimum height of the stairs that he will need to get to his roof.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n\le 100\,000$$$) — number of houses in Moomin Valley.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le 10^9$$$) — heights of houses.

Output

Print $$$n$$$ integers $$$l_i$$$ — the minimum length of the ladder with which you can climb to the roof of the $$$i$$$-th house.

Examples
Input
4
3 4 2 6
Output
2 2 2 4
Input
9
3 4 1 6 4 2 5 1 3
Output
3 3 1 2 2 2 3 1 2
Note

In the first test, there are four houses of different heights in Moomin Valley: the first house in which the Moomin family lives has a height of 3 meters, the second house belonging to Snufkin has a height of 4 meters, the third house where Baby Mu lives has a height of 2 meters, and the fourth house where the Snork Maiden lives, has a height of 6 meters.

Baby Mu will need a two-meter ladder, and she will use it to get directly from the ground to the roof of her little house. Snufkin will also need only a two-meter ladder. First, he uses it to get to the roof of Baby Mu, and then he will climb from it to his own roof. The same ladder will be needed by the Moomin family: a two-meter ladder will be enough to get first to the roof of Baby Mu, then to the roof of Snufkin. And from there, using a ladder, they will be able to descend one meter down to their own roof. The Snork Maiden, at the same time, will need a 4-meter ladder. First, she will use it to get to the roof of Baby Mu, and then she will climb from it to her own.