B. Избегайте локальных максимумов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ размера $$$n$$$. Каждый элемент этого массива представляет собой целое число от $$$1$$$ до $$$10^9$$$.

Вы можете выполнить несколько операций с этим массивом. Во время операции вы можете заменить элемент массива любым целым числом от $$$1$$$ до $$$10^9$$$.

Выведите минимальное количество необходимых операций, чтобы результирующий массив не содержал локальных максимумов, и результирующий массив после операций.

Элемент $$$a_i$$$ является локальным максимумом, если он строго больше обоих своих соседей (то есть $$$a_i > a_{i - 1}$$$ и $$$a_i > a_{i + 1}$$$). Поскольку $$$a_1$$$ и $$$a_n$$$ имеют только по одному соседу, они никогда не будут локальным максимумом.

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

Каждый тест содержит несколько тестовых случаев. Первая строка будет содержать единственное целое число $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — количество тестов. Затем следуют $$$t$$$ тестовых случаев.

Первая строка каждого теста содержит одно целое число $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ — размер массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots ,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных сначала выведите строку, содержащую одно целое число $$$m$$$ — минимальное количество требуемых операций. Затем выведите строку, состоящую из $$$n$$$ целых чисел — результирующий массив после операций. Обратите внимание, что этот массив должен отличаться ровно на $$$m$$$ элементов от исходного массива.

Если ответов несколько, выведите любой.

Пример
Входные данные
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
Примечание

В первом примере массив не содержит локального максимума, поэтому нам не нужно выполнять операции.

Во втором примере мы можем изменить $$$a_2$$$ на $$$3$$$, тогда у массива не будет локальных максимумов.