Вам дан массив \(a\) размера \(n\). Каждый элемент этого массива представляет собой целое число от \(1\) до \(10^9\).
Вы можете выполнить несколько операций с этим массивом. Во время операции вы можете заменить элемент массива любым целым числом от \(1\) до \(10^9\).
Выведите минимальное количество необходимых операций, чтобы результирующий массив не содержал локальных максимумов, и результирующий массив после операций.
Элемент \(a_i\) является локальным максимумом, если он строго больше обоих своих соседей (то есть \(a_i > a_{i - 1}\) и \(a_i > a_{i + 1}\)). Поскольку \(a_1\) и \(a_n\) имеют только по одному соседу, они никогда не будут локальным максимумом.
Выходные данные
Для каждого набора входных данных сначала выведите строку, содержащую одно целое число \(m\) — минимальное количество требуемых операций. Затем выведите строку, состоящую из \(n\) целых чисел — результирующий массив после операций. Обратите внимание, что этот массив должен отличаться ровно на \(m\) элементов от исходного массива.
Если ответов несколько, выведите любой.
Примечание
В первом примере массив не содержит локального максимума, поэтому нам не нужно выполнять операции.
Во втором примере мы можем изменить \(a_2\) на \(3\), тогда у массива не будет локальных максимумов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
2 1 2
4
1 2 3 1
5
1 2 1 2 1
9
1 2 1 3 2 3 1 2 1
9
2 1 3 1 3 1 3 1 3
|
0
2 1 2
1
1 3 3 1
1
1 2 2 2 1
2
1 2 3 3 2 3 3 2 1
2
2 1 3 3 3 1 1 1 3
|