题目描述

给定一个大小为 $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 翻译

样例

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