# B. Avoid Local Maximums Solution | Codeforces Round #772 (Div. 2)

B. Avoid Local Maximums
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

The first line of each test case contains a single integer $n$ $\left(2\le n\le 2\cdot {10}^{5}\right)$ — the size of the array $a$.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ $\left(1\le {a}_{i}\le {10}^{9}\right)$, the elements of array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

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
Copy
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
Copy
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 ${a}_{2}$ to $3$, then the array don't have local maximums.

### Solution

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1) x *= a;
a *= a;
b >>= 1;
}
return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {

int n; cin>>n;

vi v(n+1);
int ans=0;
for(int i=0; i<n; i++){
cin>>v[i];
}
if(n<=2){
cout<<0<<endl;
for(int i=0; i<n; i++)cout<<v[i]<<" ";
cout<<endl;
}
else{
for(int i=1; i<n-1; i++){
if(v[i]>v[i+1] && v[i]>v[i-1]){
v[i+1]=max(v[i],v[i+2]);
ans++;
}
}
cout<<ans<<endl;
for(int i=0; i<n; i++)cout<<v[i]<<" ";
cout<<endl;
}

}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

clock_t z = clock();

int t = 1;
cin >> t;
while (t--) solve();

return 0;
}