E. Медианный горный хребет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Берляндия — огромная страна с разнообразной географией. Одной из самых знаменитых природных достопримечательностей Берляндии является «Медианный горный хребет». Этот горный хребет представляет из себя $$$n$$$ подряд идущих горных вершин, расположенных на одной прямой, пронумерованных в порядке следования от $$$1$$$ до $$$n$$$. Высота $$$i$$$-й горной вершины равна $$$a_i$$$.

«Медианный горный хребет» знаменит тем, что с ним ежедневно происходит так называемое выравнивание горных вершин. В момент выравнивания одновременно для каждой вершины от $$$2$$$ до $$$n - 1$$$ её высота становится равна медианной высоте среди неё и двух соседних гор. А именно, если до выравнивания высоты были равны $$$b_i$$$, то новые высоты $$$a_i$$$ устроены следующим образом: $$$a_1 = b_1$$$, $$$a_n = b_n$$$, а для всех $$$i$$$ от $$$2$$$ до $$$n - 1$$$ $$$a_i = \texttt{median}(b_{i-1}, b_i, b_{i+1})$$$. Медианой трёх чисел называется второе по счёту число, если отсортировать эти три числа по возрастанию. Например, $$$\texttt{median}(5,1,2) = 2$$$, а $$$\texttt{median}(4,2,4) = 4$$$.

Недавно Берляндские учёные доказали, что какими бы ни были высоты гор, процесс выравнивания рано или поздно стабилизируется, то есть в какой-то момент высоты гор перестанут изменяться после выравнивания. Правительство Берляндии хочет понять через сколько лет это произойдёт, то есть, найти величину $$$c$$$ — сколько произойдет выравниваний, при которых у хотя бы одной горы изменится её высота. Также правительству Берляндии необходимо определить высоты гор после $$$c$$$ выравниваний, то есть узнать, какими высоты гор останутся навсегда. Помогите ученым решить эту важную задачу!

Входные данные

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 500\,000$$$) — количество гор.

Вторая строка содержит целые числа $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — текущие высоты гор.

Выходные данные

В первой строке выведите $$$c$$$ — число выравниваний вершин, при которых высота хотя бы одной горы изменится.

Во второй строке выведите $$$n$$$ чисел — итоговые высоты гор после $$$c$$$ выравниваний.

Примеры
Входные данные
5
1 2 1 2 1
Выходные данные
2
1 1 1 1 1 
Входные данные
6
1 3 2 5 4 6
Выходные данные
1
1 2 3 4 5 6 
Входные данные
6
1 1 2 2 1 1
Выходные данные
0
1 1 2 2 1 1 
Примечание

В первом примере высоты на позициях $$$1$$$ и $$$5$$$ не меняются. Так как медиана чисел $$$1$$$, $$$2$$$, $$$1$$$ это $$$1$$$, то на позициях 2 и 4 после первого выравнивания оказываются числа 1, и так как медиана чисел $$$2$$$, $$$1$$$, $$$2$$$ это $$$2$$$, то на позиции 3 после первого выравнивания оказывается число 2. Итого после первого выравнивания горных вершин горы имеют высоты $$$1$$$, $$$1$$$, $$$2$$$, $$$1$$$, $$$1$$$. После второго выравнивания высоты становятся $$$1$$$, $$$1$$$, $$$1$$$, $$$1$$$, $$$1$$$ и дальше они меняться не будут, соответственно всего было $$$2$$$ меняющих высоты выравнивания.

В третем примере после выравнивания ни у одной горы её высота не изменится и число выравниваний, при которых высоты изменятся, равно $$$0$$$.