CF1635B - Avoid Local Maximums

You are given an array a of size n. Each element in this array is an integer between 1 and 109.

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

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 ai is a local maximum if it is strictly larger than both of its neighbors (that is, ai>ai−1 and ai>ai+1). Since a1 and an have only one neighbor each, they will never be a local maximum.

Input

Each test contains multiple test cases. The first line will contain a single integer t (1≤t≤10000) — the number of test cases. Then t test cases follow.

The first line of each test case contains a single integer n (2≤n≤2⋅105) — the size of the array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109), the elements of array.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

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.

Example

input

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

output

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

Note

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 a2 to 3, then the array don't have local maximums.

中文翻译：

给定一个大小为 n 的数组 a。 该数组中的每个元素都是 1 到 109 之间的整数。

您可以对此数组执行多项操作。 在操作过程中，您可以将数组中的元素替换为 1 到 109 之间的任何整数。

输出所需的最小操作数，以使结果数组不包含任何局部最大值，以及操作后的结果数组。

如果元素 ai 严格大于其两个邻居（即 ai>ai−1 且 ai>ai+1），则该元素 ai 是局部最大值。 由于 a1 和 an

  每个都只有一个邻居，它们永远不会是局部最大值。

输入

每个测试包含多个测试用例。 第一行将包含一个整数 t (1≤t≤10000) — 测试用例的数量。 然后

  测试用例如下。

每个测试用例的第一行包含一个整数 n (2≤n≤2⋅105) — 数组 a 的大小。

每个测试用例的第二行包含n个整数a1,a2,…,an  (1≤ai≤109)，数组的元素。

保证所有测试用例的 n 之和不超过 2⋅105。

输出

对于每个测试用例，首先输出一行包含单个整数 m

  ——所需的最少操作次数。 然后输出一行由 n 个整数组成的行——运算后的结果数组。 请注意，此数组与初始数组应恰好有 m 个元素不同。

如果有多个答案，请打印其中一个。

----------------------------------------------------------------

当我们遇到一个比两边数字都大的位置的时候，我们要把后面的数字改为最大值，后面的数字改成后面数字左右的最大值，当然如果是最后一个，特例判断即可，剩下就是记录这种情况的次数，然后输出数组；

下面是代码：