The photography contest for the UNAL portfolio cover page is nearly over and Paula, as a big fan of photography, is worried since she still does not have a great picture to participate with. This is because this semester has been unusually harder than the previous one.
Paula is a fit girl. She usually goes to the GYM to be in shape but it seems that today she won't be able to go. That's why she decided that while she will be looking for the best picture, she will try to walk as much as she can.
Paula thinks that the best photo she can take will be at the top of some building. And she considers that it's not necessary to take a photo in a building whose height is less or equal than the height of the building where she is right now.
After Paula takes pictures at the top of a building, she chooses the next building to visit to take more photos. Naturally, she will choose only among the buildings that she is able to see. A building is in Paula's sight if and only if there is no other strictly higher building in between.
All Buildings in the UNAL are located in a single line, one after another. The distance that she is going to walk from one building to another is the absolute difference between the positions of the buildings in the line e.g. to go from building $i$ to building $j$ she needs to walk $| i -j |$ distance.
Paula is planning at which building she should start taking pictures. That's why she wants to know, for each building, what is the maximum distance she would walk if she starts to take pictures in that building. Can you help Paula with that?
The first line contains an integer $n$ ($1 <= n <= 10^5$) — The number of buildings.
The following line will contain $n$ integers ($1 <= h_i <= 10^9$) — The height of the $i$-th building.
Print $n$ numbers on a line. The $i$-th number is the maximum distance Paula would walk if she starts taking pictures at building $i$.
## Input
The first line contains an integer $n$ ($1 <= n <= 10^5$) — The number of buildings.The following line will contain $n$ integers ($1 <= h_i <= 10^9$) — The height of the $i$-th building.
## Output
Print $n$ numbers on a line. The $i$-th number is the maximum distance Paula would walk if she starts taking pictures at building $i$.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of buildings.
Let $ H = (h_1, h_2, \dots, h_n) $ be a sequence of building heights, where $ h_i \in \mathbb{Z}^+ $ is the height of building $ i $, for $ i \in \{1, \dots, n\} $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le h_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each building $ i \in \{1, \dots, n\} $, define the set $ S_i $ of reachable buildings starting from $ i $ as follows:
- $ i \in S_i $,
- For any $ j \in S_i $, $ j \ne i $, there exists a sequence $ i = i_0, i_1, \dots, i_k = j $ such that for all $ \ell \in \{1, \dots, k\} $:
- $ h_{i_\ell} > h_{i_{\ell-1}} $,
- and there is no building $ m $ strictly between $ i_{\ell-1} $ and $ i_\ell $ with $ h_m > h_{i_{\ell-1}} $.
The distance walked from $ i $ to $ j $ is $ |i - j| $.
Let $ D_i = \max \{ |i - j| \mid j \in S_i \} $.
Output $ (D_1, D_2, \dots, D_n) $.