Задача №114737. Медианный горный хребет
Берляндия — огромная страна с разнообразной географией. Одной из самых знаменитых природных достопримечательностей Берляндии является «Медианный горный хребет». Этот горный хребет представляет из себя \(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})\). Медианой трёх чисел называется второе по счёту число, если отсортировать эти три числа по возрастанию. Например, \(median(5,1,2) = 2\), а \(median(4,2,4) = 4\).
Недавно Берляндские учёные доказали, что какими бы ни были высоты гор, процесс выравнивания рано или поздно стабилизируется, то есть в какой-то момент высоты гор перестанут изменяться после выравнивания. Правительство Берляндии хочет понять через сколько лет это произойдёт, то есть, найти величину \(c\) — сколько произойдет выравниваний, при которых у хотя бы одной горы изменится её высота. Помогите ученым решить эту важную задачу!
Обратите внимание, что в некоторых группах тестов помимо значения \(c\) вам необходимо определить также и высоты гор после \(c\) выравниваний, то есть узнать, какими высоты гор останутся навсегда.
Первая строка содержит целые числа \(n\) и \(t\) (\(1 \le n \le 500\,000\), \(0 \le t \le 1\)) — количество гор и параметр, который определяет, необходимо ли определить итоговые высоты гор.
Вторая строка содержит целые числа \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — текущие высоты гор.
В первой строке выведите \(c\) — число выравниваний вершин, при которых высота хотя бы одной горы изменится.
Если \(t = 1\), то во второй строке выведите \(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\). Так как \(t = 0\), то выводить итоговые высоты гор не нужно.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(a_i\) | \(t\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 19 | \(n \le 1000\) | – | – | 0 | Гарантируется, что \(c \le 10\,000\). |
| 2 | 24 | – | \(a_i \le 2\) | – | – | |
| 3 | 14 | – | \(a_i \le 100\) | \(t=0\) | – | |
| 4 | 14 | – | \(a_i \le 100\) | – | 0, 2, 3 | |
| 5 | 14 | – | – | \(t =0\) | 3 | |
| 6 | 15 | – | – | – | 0, 1, 2, 3, 4, 5 | Offline-проверка. |
5 1 1 2 1 2 1
2 1 1 1 1 1
6 1 1 3 2 5 4 6
1 1 2 3 4 5 6
6 0 1 1 2 2 1 1
0