Avoid Local Maximums
Contest: Codeforces Round 772 (Div. 2)
Difficulty rating: 800
Tags: greedy

You are given an array $$$a$$$ of size $$$n$$$. Each element in this array is an integer between $$$1$$$ and $$$10^9$$$.

You can perform several operations to this array. During an operation, you can replace an element in the array with any integer between $$$1$$$ and $$$10^9$$$.

Output the minimum number of operations needed such that the resulting array doesn't contain any local maximums, and the resulting array after the operations.

An element $$$a_i$$$ is a local maximum if it is strictly larger than both of its neighbors (that is, $$$a_i > a_{i - 1}$$$ and $$$a_i > a_{i + 1}$$$). Since $$$a_1$$$ and $$$a_n$$$ have only one neighbor each, they will never be a local maximum.

Input format:
Each test contains multiple test cases. The first line will contain a single integer $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots ,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$, the elements of array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, first output a line containing a single integer $$$m$$$ — minimum number of operations required. Then ouput a line consist of $$$n$$$ integers — the resulting array after the operations. Note that this array should differ in exactly $$$m$$$ elements from the initial array.

If there are multiple answers, print any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the array contains no local maximum, so we don't need to perform operations.

In the second example, we can change $$$a_2$$$ to $$$3$$$, then the array don't have local maximums.

Example input:
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

Example output:
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

Editorial:
Let's check all elements in $$$a$$$ from the left.
Once we find that $$$a_i$$$ is a local maximum, then we should perform an operation to fix it. There are many ways to do this, but the optimal way is to set $$$a_{i+1}$$$ to $$$max(a_{i},a_{i+2})$$$, because we can avoid $$$a_i$$$ and $$$a_{i+2}$$$ from being local maximums at the same time.
Proof: Let's take all indices of local maximums in the initial array and append them to an empty array $$$b$$$ with their corresponding order. For example, if $$$a=[1,2,1,3,1,1,3,1,4,1,2 ,1]$$$, we obtain $$$b=[2,4,7,9,11]$$$. Then, we devide $$$b$$$ into subarrays, such that $$$b_i$$$ and $$$b_{i+1}$$$ are in the same subarray if and only if $$$b_{i+1}-b_i=2$$$. Using the same example above, we will devide $$$b$$$ into $$$[2,4], [7,9,11]$$$. To finish our proof, we need two important observations.
1. Any operation would cancel at most two local maximums.
2. Any operation won't cancel two local maximums whose indices are in different subarrays of $$$b$$$.
So for a fixed subarray, we need at least $$$\lceil \frac{length}{2} \rceil $$$ operations to cancel all corresponding local maximums, and the lower bound of the answer is the sum of $$$\lceil \frac{length}{2} \rceil $$$ for all subarrays.
Since the strategy described above could achieve this lower bound, our proof has completed.