Median Mountain Range
Contest: Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 3300
Tags: data structures

Berland — is a huge country with diverse geography. One of the most famous natural attractions of Berland is the "Median mountain range". This mountain range is $$$n$$$ mountain peaks, located on one straight line and numbered in order of $$$1$$$ to $$$n$$$. The height of the $$$i$$$-th mountain top is $$$a_i$$$.

"Median mountain range" is famous for the so called alignment of mountain peaks happening to it every day. At the moment of alignment simultaneously for each mountain from $$$2$$$ to $$$n - 1$$$ its height becomes equal to the median height among it and two neighboring mountains. Formally, if before the alignment the heights were equal $$$b_i$$$, then after the alignment new heights $$$a_i$$$ are as follows: $$$a_1 = b_1$$$, $$$a_n = b_n$$$ and for all $$$i$$$ from $$$2$$$ to $$$n - 1$$$ $$$a_i = \texttt{median}(b_{i-1}, b_i, b_{i+1})$$$. The median of three integers is the second largest number among them. For example, $$$\texttt{median}(5,1,2) = 2$$$, and $$$\texttt{median}(4,2,4) = 4$$$.

Recently, Berland scientists have proved that whatever are the current heights of the mountains, the alignment process will stabilize sooner or later, i.e. at some point the altitude of the mountains won't changing after the alignment any more. The government of Berland wants to understand how soon it will happen, i.e. to find the value of $$$c$$$ — how many alignments will occur, which will change the height of at least one mountain. Also, the government of Berland needs to determine the heights of the mountains after $$$c$$$ alignments, that is, find out what heights of the mountains stay forever. Help scientists solve this important problem!

Input format:
The first line contains integers $$$n$$$ ($$$1 \le n \le 500\,000$$$) — the number of mountains.

The second line contains integers $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — current heights of the mountains.

Output format:
In the first line print $$$c$$$ — the number of alignments, which change the height of at least one mountain.

In the second line print $$$n$$$ integers — the final heights of the mountains after $$$c$$$ alignments.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, the heights of the mountains at index $$$1$$$ and $$$5$$$ never change. Since the median of $$$1$$$, $$$2$$$, $$$1$$$ is $$$1$$$, the second and the fourth mountains will have height 1 after the first alignment, and since the median of $$$2$$$, $$$1$$$, $$$2$$$ is $$$2$$$, the third mountain will have height 2 after the first alignment. This way, after one alignment the heights are $$$1$$$, $$$1$$$, $$$2$$$, $$$1$$$, $$$1$$$. After the second alignment the heights change into $$$1$$$, $$$1$$$, $$$1$$$, $$$1$$$, $$$1$$$ and never change from now on, so there are only $$$2$$$ alignments changing the mountain heights.

In the third examples the alignment doesn't change any mountain height, so the number of alignments changing any height is $$$0$$$.

Example input:
5
1 2 1 2 1

Example output:
2
1 1 1 1 1

Example input:
6
1 3 2 5 4 6

Example output:
1
1 2 3 4 5 6

Editorial:
Let's assume that $$$1 \le a_i \le 2$$$. We can notice that if for some $$$i$$$ $$$a_i = a_{i + 1}$$$, than on $$$i$$$-th and $$$(i+1)$$$-th positions numbers will stay the same forever. So the only changes will happen to segments of consecutive alternating $$$1$$$ and $$$2$$$. Now let's look what will happen to such segments after first alignment of mountain peaks. The beginning and end of segment will stay the same, and all intermediate number will change ($$$1$$$ will change to $$$2$$$ and $$$2$$$ will change to $$$1$$$). So the second number will be equal to first and pre last number will be equal to last. That means that lengths of all segments of consecutive alternating $$$1$$$ and $$$2$$$ will decrease by $$$2$$$. So the number of alignments equals to length of longest segment divided by $$$2$$$, and for each segment its first half will be equal to beginning of segment, and its second half will be equal to the end of segment.
Now let's fix some number $$$x$$$ and create array $$$b$$$, where $$$b_i = 1$$$ if $$$a_i < x$$$ and $$$b_i = 2$$$ if $$$a_i \ge x$$$. It can be observed, that if we will make alignment with initial mountain heights and replace them with $$$1$$$ and $$$2$$$ the same way, we will get array $$$b$$$ after first alignment. So if we will get array $$$b$$$ after stabilization, we will know that on positions where $$$b_i = 1$$$ mountains will have height less than $$$x$$$, and on positions where $$$b_i = 2$$$ the mountain heights after stabilization will be grater or equal than $$$x$$$. So to get the number of alignments we will need to find the longest segment of consecutive alternating $$$1$$$ and $$$2$$$ for all possible $$$x$$$.
Now we need to get the final heights. Let's assume that we know all positions where final heights will be grater than $$$x$$$. Let's create array $$$b$$$ the same way as described above. Using this array we can get positions where the mountain heights will be grater or equal than $$$x$$$ after stabilization. As we know positions where the heights will be grater than $$$x$$$, we can get positions where heights will be equal to $$$x$$$. So if we will decrease $$$x$$$ from maximum value to $$$1$$$, we can get the final heights of all mountains.
To perform it quick enough, we can consider only those $$$x$$$, that equal to some of existing initial heights. Then we can decrease $$$x$$$ and in some set store all segments of consecutive alternating $$$1$$$ and $$$2$$$ in array $$$b$$$ for such $$$x$$$. When the $$$x$$$ is decreased, on some positions $$$1$$$ can change to $$$2$$$. The changes can happen only to the segments that have such positions. (The segments can be splited by this position, or this position can be merged with neighbouring segment(s)) So in total there will be $$$O(n)$$$ changes to segments, and we can perform all of them in $$$O(n \log n)$$$ time. Also we can store in set all positions, for which we do not know the final heights, we for each new segment we can find positions where $$$1$$$ will be in the end (it will be some segment of consecutive positions) and search free positions among them in the set. In total it will take $$$O(n \log n)$$$ time.
There also exists solution in $$$O(n)$$$ time.