Avoid Local Maximums
Description
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.
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$.
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.
Input
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
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.
Samples
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
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.