给定一个数组 $$$a$$$,大小为 $$$n$$$。该数组中的每个元素都是 $$$1$$$ 和 $$$10^9$$$ 之间的整数。
您可以对此数组执行多项操作。在操作过程中,您可以将数组中的元素替换为 $$$1$$$ 和 $$$10^9$$$ 之间的任何整数。
输出所需的最小操作数,以使结果数组不包含任何局部最大值,以及操作后的结果数组。
如果元素 $$$a_i$$$ 严格大于其两个邻居(即 $$$a_i > a_{i - 1}$$$ 和 $$$a_i > a_{i + 1}$$$),则该元素是局部最大值。由于 $$$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$$$ 整数组成 - 操作后的结果数组。请注意,此数组与初始数组的元素应完全相同。
如果有多个答案,请打印其中一个。
示例
输入 #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
输出 #1
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
注意
在第一个示例中,数组不包含局部最大值,因此我们不需要执行操作。
在第二个例子中,我们可以将 $$$a_2$$$ 更改为 $$$3$$$,那么数组就没有局部最大值。