Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

F. Wildfires
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanchali is a researcher who wants to protect an endangered species of trees. Their habitat consists of $$$n$$$ forests arranged in a line, where the $$$i$$$-th forest has a density of $$$t_i$$$.

Unfortunately, this habitat is very vulnerable to wildfires. A forest is either healthy or is burning with a wildfire of some integer strength $$$k \gt 0$$$. Wildfires can spread to adjacent forests (forests $$$i$$$ and $$$j$$$ are adjacent if $$$\lvert i - j \rvert = 1$$$).

For a pair of adjacent forests $$$i$$$ and $$$j$$$, if forest $$$i$$$ is healthy but forest $$$j$$$ has a wildfire of strength $$$k$$$, then a wildfire of strength $$$k'$$$ starts in forest $$$i$$$, where

$$$k' = \begin{cases} k+1 & k \lt t_i \\ k & k = t_i \\ k-1 & k \gt t_i \\ \end{cases} $$$

If $$$k' = 0$$$, no fire starts.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, find the minimum strength needed for a wildfire to start at forest $$$i$$$ and burn all of the $$$n$$$ forests in the habitat.

Input

The first line of the input will contain an integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) representing the number of forests.

The second line will contain $$$n$$$ integers $$$t_1 \dots t_n$$$ ($$$0 \leq t_i \leq n$$$) representing the density of trees in each forest.

Output

Print $$$n$$$ integers representing the minimum strength needed for a wildfire to start at each forest and burn all the forests in the habitat.

Example
Input
7
0 0 3 1 2 0 5
Output
2 2 3 2 3 4 5
Note

In the sample, a wildfire starting at forest $$$1$$$ can burn all of the $$$n$$$ forests with strength $$$2$$$.

  • Forest $$$2$$$: a wildfire with strength $$$1$$$ starts
  • Forest $$$3$$$: a wildfire with strength $$$2$$$ starts
  • Forest $$$4$$$: a wildfire with strength $$$1$$$ starts
  • Forest $$$5$$$: a wildfire with strength $$$2$$$ starts
  • Forest $$$6$$$: a wildfire with strength $$$1$$$ starts
  • Forest $$$7$$$: a wildfire with strength $$$2$$$ starts

Thus, the wildfire will reach all $$$n$$$ forests. On the other hand, if a wildfire with strength $$$1$$$ started at forest $$$1$$$, it would not be able to spread to forest $$$2$$$.