+ Time Limit: 1 second + Memory Limit: 256 MB -------------------- Amirhosein has a piece of land consisting of $n$ consecutive sections. The height of section $i$ is $a_i$, and the array $a$ is a permutation of the numbers from $1$ to $n$. We call a section a **pit** if its height is smaller than the heights of all of its neighboring sections. In other words, if a section has no neighbors, it is always a pit; if it has exactly one neighbor, it is a pit if it is shorter than that neighbor; and if it has two neighbors, it must be shorter than both of them. Now, Amirhosein has a ball on every section of the land. For each ball, he wants to know the minimum amount of time needed for the ball to enter a pit if it is rolled from its initial section in either the **left or right** direction. A ball may fail to reach any pit when started in one of the two directions, but it is guaranteed that every ball can reach a pit in at least one of the two possible directions. If the ball is initially in a pit, the answer is $0$. Once a ball starts rolling in a direction, it never changes direction. While rolling in a particular direction, if the height of the section where the ball currently is is greater than the height of the next section in that direction, the ball rolls into that adjacent section. Each move to an adjacent section takes **1 unit of time**. For every section, find the minimum time required for the ball placed on that section to enter a pit. # Input The first line contains a single integer $n$. $$1 \le n \le 2*10^5$$ The second line contains $n$ integers, where the $i$-th integer denotes the height of the $i$-th section of the land. $$1 \le a_i \le n$$ The array $a$ is a permutation of the numbers from $1$ to $n$, and no two sections have the same height. # Output Print $n$ integers in one line. The $i$-th integer should be the minimum time required for the ball placed on section $i$ to enter a pit. # Example ## Sample Input 1 ``` 7 2 3 6 7 4 1 5 ``` ## Sample Output 1 ``` 0 1 2 2 1 0 1 ```