CF1635B.Avoid Local Maximums

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 \gt a_{i - 1}$ and $a_i \gt a_{i + 1}$). Since $a_1$ and $a_n$ have only one neighbor each, they will never be a local maximum.

给你一个大小为 $n$ 的数组 $a$。该数组中的每个元素均为 $1$ 到 $10^9$ 之间的整数。

你可以对该数组执行若干次操作。每次操作中，你可以将数组中的某个元素替换为 $1$ 到 $10^9$ 之间的任意整数。

请输出使得最终数组中不包含任何局部最大值所需的最少操作次数，以及执行这些操作后得到的数组。

若某个元素 $a_i$ 严格大于其两侧相邻元素（即 $a_i \gt a_{i - 1}$ 且 $a_i \gt a_{i + 1}$），则称其为局部最大值。由于 $a_1$ 和 $a_n$ 各只有一个邻居，因此它们永远不会成为局部最大值。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

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.

对于每个测试用例，首先输出一行，包含一个整数 $m$ —— 所需的最少操作次数。然后输出一行，包含 $n$ 个整数 —— 经过操作后得到的数组。注意，该数组应恰好与初始数组在 $m$ 个元素上不同。

如果存在多个答案，输出任意一个即可。

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.

在第一个例子中，数组不包含任何局部最大值，因此无需执行任何操作。

在第二个例子中，我们可以将 $a_2$ 修改为 $3$，此时数组不再含有局部最大值。