Rightplant

There are $N$ buildings in a row, each with a distinct integer height from $1$ to $N$. The height of the $i$-th building from the left is $H_i$.

If a branch is fired to the right from a building of height $h$, the branch flies over buildings whose height is at most $h$. When the branch hits a building taller than $h$, that building's height decreases by $1$, and the branch reverses direction.

A branch fired right from a building of height $h$ flies over a building shorter than $h$

A branch fired right from a building of height $h$ flies over a building of height $h$

A branch fired right from a building of height $h$ hits a building taller than $h$ and reverses direction

Fire a branch to the right from the $i$-th building from the left. Let $B_i$ be the number of times that branch changes direction until it flies past the leftmost or rightmost building. Find the sequence $H$ that maximizes $B_1 + B_2 + \dots + B_N$.

The first line contains an integer $N$. ($2 \le N \le 5\,000$)

Print the elements $H_1, H_2, \dots, H_N$ of a sequence $H$ that maximizes $B_1 + B_2 + \dots + B_N$, separated by spaces. If there are several such sequences, print any of them.