CF1635B Avoid Local Maximums

给定一个大小为 $n$ 的数组 $a$，数组中的每个元素都是 $1$ 到 $10^9$ 之间的整数。 你可以对该数组进行若干次操作。每次操作时，你可以将数组中的任意一个元素替换为 $1$ 到 $10^9$ 之间的任意整数。 请输出使得最终数组中不包含任何局部极大值所需的最少操作次数，以及操作后的数组。 如果某个元素 $a_i$ 严格大于它的两个相邻元素（即 $a_i > a_{i-1}$ 且 $a_i > a_{i+1}$），则称 $a_i$ 是一个局部极大值。由于 $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$ 个元素不同。 如果有多种答案，输出任意一种均可。

在第一个样例中，数组中没有局部极大值，因此不需要进行任何操作。 在第二个样例中，可以将 $a_2$ 改为 $3$，此时数组中没有局部极大值。 由 ChatGPT 4.1 翻译