Берляндия — огромная страна с разнообразной географией. Одной из самых знаменитых природных достопримечательностей Берляндии является «Медианный горный хребет». Этот горный хребет представляет из себя \(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\) выравниваний, то есть узнать, какими высоты гор останутся навсегда. Помогите ученым решить эту важную задачу!
Выходные данные
В первой строке выведите \(c\) — число выравниваний вершин, при которых высота хотя бы одной горы изменится.
Во второй строке выведите \(n\) чисел — итоговые высоты гор после \(c\) выравниваний.
Примечание
В первом примере высоты на позициях \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 1 2 1
|
2
1 1 1 1 1
|
|
2
|
6
1 3 2 5 4 6
|
1
1 2 3 4 5 6
|
|
3
|
6
1 1 2 2 1 1
|
0
1 1 2 2 1 1
|