Avoid Local Maximums

给定一个长度为 $n$ 的数组 $a$。你可以执行若干次操作，每次操作中，你可以选择数组中任意一个元素 $a_i$，并将其替换为任意一个大于等于 $1$ 且小于等于 $10^9$ 的整数。 我们说数组中的某一个元素 $a_i$ 是局部最大的，当且仅当 $a_i>a_{i-1}$ 且 $a_i>a_{i+1}$。特别地，$a_1$ 和 $a_n$ 永远都不是局部最大的。 请求出使得数组 $a$ 中不存在局部最大的元素的最小操作次数 $m$，并输出任意一个执行 $m$ 次操作得到的数组。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $2\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

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.

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

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.