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

## 输入输出格式

### 输入格式

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

### 输出格式

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.

## 输入输出样例

### 输入样例 #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

## 说明

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.