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


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


-----Examples-----

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

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms


Solutions:
from enum import Enum, auto
import copy
import sys
import math
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		res = 0
		copy_a = copy.copy(a)
		prev_1 = a[1]
		prev_2 = a[0]
		for (i, ai) in enumerate(a):
			if i == 0 or i == 1:
				continue
			if prev_2 < prev_1 and prev_1 > ai:
				res += 1
				if i + 1 < n and ai < a[i + 1] and (a[i + 1] > prev_1):
					copy_a[i] = a[i + 1]
					prev_2 = prev_1
					prev_1 = a[i + 1]
				else:
					copy_a[i] = prev_1
					prev_2 = prev_1
			else:
				prev_2 = prev_1
				prev_1 = ai
		print(res)
		print(' '.join(map(str, copy_a)))
main()


import sys
import math

def mp():
	return map(int, sys.stdin.readline().split())

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def main(tc: int):
	n = ri()
	a = ria()
	cnt = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i == n - 2:
				a[i + 1] = a[i]
			else:
				a[i + 1] = max(a[i], a[i + 2])
			cnt += 1
	wi(cnt)
	wia(a)
t = ri()
for tc in range(1, t + 1):
	main(tc)


def func(a):
	m = 0
	for i in range(1, len(a) - 1):
		if a[i - 1] < a[i] and a[i] > a[i + 1]:
			m += 1
			if i + 2 > len(a) - 1 or a[i + 2] <= a[i]:
				a[i + 1] = a[i]
			else:
				a[i + 1] = a[i + 2]
	return (m, a)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	(m, arr) = func(a)
	print(m)
	print(' '.join([str(x) for x in arr]))


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		cnt = 0
		for i in range(1, n - 1):
			if arr[i - 1] < arr[i] > arr[i + 1]:
				if i == n - 2:
					arr[i + 1] = arr[i]
				else:
					arr[i + 1] = max(arr[i], arr[i + 2])
				cnt += 1
		print(cnt)
		print(' '.join([str(i) for i in arr]))
main()


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	r = 0
	for i in range(4, n):
		if a[i - 1] > a[i] and a[i - 2] < a[i - 1] and (a[i - 3] > a[i - 2]) and (a[i - 4] < a[i - 3]):
			if a[i - 3] <= a[i - 1]:
				a[i - 2] = a[i - 1]
			else:
				a[i - 2] = a[i - 3]
			r += 1
	for i in range(2, n):
		if a[i - 1] > a[i - 2] and a[i - 1] > a[i]:
			if a[i - 2] >= a[i]:
				a[i - 1] = a[i - 2]
			else:
				a[i - 1] = a[i]
			r += 1
	print(r)
	print(' '.join(map(str, a)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
GAP = 2
for t in [wtf[i:i + GAP] for i in range(1, len(wtf), GAP)]:
	N = int(t[0])
	A = list(map(int, t[1].split()))
	ans = 0
	aM = max(A)
	for i in range(1, N - 1):
		if A[i] > A[i - 1] and A[i] > A[i + 1]:
			if i + 2 < N:
				A[i + 1] = max(A[i], A[i + 2])
			else:
				A[i + 1] = A[i]
			ans += 1
	print(f"{ans}\n{' '.join(map(str, A))}")


n = int(input())
for i in range(n):
	x = int(input())
	t = list(map(int, input().split()))
	c = 0
	m = max(t)
	for i in range(1, x - 1):
		if t[i - 1] < t[i] and t[i] > t[i + 1]:
			c += 1
			if i + 2 < x:
				t[i + 1] = max(t[i], t[i + 2])
			else:
				t[i + 1] = t[i]
	print(c)
	s = ' '.join(map(str, t))
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	le = -1
	for i in range(1, len(a) - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if le == i - 1:
				a[i - 1] = a[i]
				le = i - 1
			else:
				cnt += 1
				a[i + 1] = a[i]
				le = i + 1
	print(cnt)
	ans = map(str, a)
	print(' '.join(ans))


def solve(a, n):
	count = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i < n - 2:
				a[i + 1] = max(a[i], a[i + 2])
				count += 1
			else:
				a[i + 1] = a[i]
				count += 1
	print(count)
	print(' '.join([str(num) for num in a]))
p = int(input())
for _ in range(p):
	n = int(input())
	a = [int(num) for num in input().split()]
	solve(a, n)


def solve(nums):
	num_changes = 0
	for i in range(1, len(nums) - 1):
		if nums[i - 1] < nums[i] and nums[i] > nums[i + 1]:
			num_changes += 1
			if i == len(nums) - 2:
				nums[i + 1] = nums[i]
			else:
				nums[i + 1] = max(nums[i], nums[i + 2])
	print(num_changes)
	print(' '.join([str(n) for n in nums]))
T = int(input())
for _ in range(T):
	n = int(input())
	nums = [int(x) for x in input().split()]
	solve(nums)


from copy import deepcopy
ans = []
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	operations = 0
	for i in range(1, len(arr) - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			operations += 1
			if len(arr) - 1 >= i + 2:
				arr[i + 1] = max(arr[i], arr[i + 2])
			else:
				arr[i + 1] = arr[i]
	ans.append([operations, arr])
for x in ans:
	print(x[0])
	print(' '.join((str(i) for i in x[1])))


T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	op = 0
	for i in range(1, N - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			op += 1
			if i < N - 2:
				arr[i + 1] = max(arr[i], arr[i + 2])
			else:
				arr[i + 1] = arr[i]
	print(op)
	print(' '.join(list(map(str, arr))))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	diff = 0
	replace = False
	for i in range(1, n - 1):
		if replace:
			arr[i] = max(arr[i - 1], arr[i + 1])
			replace = False
		if arr[i] > arr[i + 1] and arr[i] > arr[i - 1]:
			replace = True
			diff += 1
	if replace:
		arr[n - 1] = arr[n - 2]
	print(diff)
	print(' '.join(map(str, arr)))


for t in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	sm = 0
	for i in range(1, n - 1):
		if ls[i] > ls[i - 1] and ls[i] > ls[i + 1]:
			if i + 2 < n:
				ls[i + 1] = max(ls[i], ls[i + 2])
			else:
				ls[i + 1] = ls[i]
			sm += 1
	print(sm)
	print(' '.join(list(map(str, ls))))


t = int(input())
outs = []
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			s += 1
			if i < n - 2:
				a[i + 1] = max(a[i], a[i + 2])
			else:
				a[i + 1] = a[i]
	for q in range(len(a)):
		a[q] = str(a[q])
	outs.append(s)
	strlist = ' '.join(a)
	outs.append(strlist)
for i in outs:
	print(i)


import sys
import math
strInp = lambda : input().strip().split()
intInp = lambda : list(map(int, strInp()))
for t in range(int(input())):
	n = int(input())
	arr = intInp()
	count = 0
	for i in range(1, n - 1):
		if arr[i] > arr[i + 1] and arr[i] > arr[i - 1]:
			count += 1
			if i + 2 >= n:
				arr[i + 1] = arr[i]
				break
			if arr[i + 2] >= arr[i]:
				arr[i + 1] = arr[i + 2]
			else:
				arr[i + 1] = arr[i]
	print(count)
	print(' '.join((str(e) for e in arr)))


t = int(input())
for _ in range(t):
	input()
	arr = [int(x) for x in input().split()]
	total_ops = 0
	for i in range(1, len(arr) - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			arr[i + 1] = max(arr[i:i + 3])
			total_ops += 1
	print(total_ops)
	print(' '.join((str(num) for num in arr)))


loopcount = int(input())
for loop in range(loopcount):
	a = int(input())
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	output = 0
	for i in range(1, a - 1):
		if x[i] > x[i - 1] and x[i] > x[i + 1]:
			output += 1
			if i + 2 < a and x[i + 2] > x[i]:
				x[i + 1] = x[i + 2]
			else:
				x[i + 1] = x[i]
	print(output)
	string_ints = [str(int) for int in x]
	print(' '.join(string_ints))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	i = 1
	c = 0
	while i < n - 1:
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			if i + 2 < n:
				arr[i + 1] = max(arr[i], arr[i + 2])
				c += 1
			else:
				arr[i + 1] = arr[i]
				c += 1
		i += 1
	print(c)
	strng = ' '.join([str(x) for x in arr])
	print(strng)


n = int(input())
for i in range(n):
	k = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for j in range(k - 2):
		if arr[j + 1] > arr[j] and arr[j + 1] > arr[j + 2]:
			try:
				if arr[j + 3] > arr[j + 1]:
					arr[j + 2] = arr[j + 3]
				else:
					arr[j + 2] = arr[j + 1]
			except:
				arr[j + 2] = arr[j + 1]
			count += 1
	print(count)
	print(' '.join(map(str, arr)))


t = int(input())
result = []
resInd = 0
for j in range(0, t):
	n = int(input())
	dataStr = input()
	counter = 0
	intDataSet = [int(i) for i in dataStr.split(' ')]
	for i in range(1, len(intDataSet) - 1):
		if intDataSet[i] > intDataSet[i - 1] and intDataSet[i] > intDataSet[i + 1]:
			counter += 1
			if i + 2 < len(intDataSet):
				intDataSet[i + 1] = max(intDataSet[i], intDataSet[i + 2])
			else:
				intDataSet[i + 1] = intDataSet[i]
	result.append(counter)
	strR = ' '.join(map(str, intDataSet))
	result.append(strR)
	counter = 0
for i in range(0, len(result), 2):
	print(result[i])
	print(result[i + 1])


def sol(A):
	maxx = []
	for i in range(1, len(A) - 1):
		if A[i - 1] < A[i] > A[i + 1]:
			maxx.append(i)
	count = 0
	i = 0
	while i < len(maxx):
		if i < len(maxx) - 1 and maxx[i] + 2 == maxx[i + 1]:
			j = maxx[i] + 1
			A[j] = max(A[j - 1], A[j + 1])
			count += 1
			i += 2
		else:
			j = maxx[i]
			A[j] = max(A[j - 1], A[j + 1])
			count += 1
			i += 1
	return (count, A)
x = int(input())
for _ in range(x):
	n = int(input())
	A = list(map(int, input().split()))
	(count, ans) = sol(A)
	print(count)
	print(' '.join(map(str, ans)))


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	max_index = []
	for i in range(1, len(l) - 1):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			max_index.append(i)
	if len(max_index) == 0:
		res.append([0, l])
	else:
		change = 0
		i = 0
		while i < len(max_index):
			idx = max_index[i]
			if i + 1 < len(max_index) and max_index[i + 1] == idx + 2:
				change += 1
				l[idx + 1] = max(l[idx], l[idx + 2])
				i += 2
			else:
				change += 1
				l[idx] = max(l[idx - 1], l[idx + 1])
				i += 1
		res.append([change, l])
for r in res:
	print(r[0])
	rs = [str(k) for k in r[1]]
	print(' '.join(rs))


def non_max(a):
	result = a.copy()
	n = len(a)
	maximums = []
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			maximums.append([i, a[i]])
	count = 0
	n_maximums = len(maximums)
	j = 0
	while j < n_maximums:
		(index, value) = maximums[j]
		if j < n_maximums - 1:
			(index2, value2) = maximums[j + 1]
			if index2 == index + 2:
				count += 1
				result[index + 1] = max(value, value2)
				j += 2
				continue
		count += 1
		result[index] = max(result[index - 1], result[index + 1])
		j += 1
	return (count, result)
n_t = int(input())
for t in range(n_t):
	n = int(input())
	aa = list(map(int, input().split(' ')))
	assert len(aa) == n
	(count, result) = non_max(aa)
	print(count)
	print(' '.join(map(str, result)))


def find(arr):
	i = 1
	count = 0
	while i < len(arr) - 1:
		if arr[i - 1] < arr[i] and arr[i + 1] < arr[i]:
			if i + 2 < len(arr):
				arr[i + 1] = max(arr[i], arr[i + 2])
			else:
				arr[i + 1] = arr[i]
			count += 1
		i += 1
	s = ' '.join([str(x) for x in arr])
	return (count, s)
num = int(input())
for i in range(num):
	n = input()
	arr = [int(x) for x in input().split()]
	(count, result) = find(arr)
	print(count)
	print(result)


from re import A
x = input()
x = int(x)
for i in range(x):
	min_oper = 0
	y = input()
	y = int(y)
	array_to_fix = list(map(int, input().split()))
	for k in range(1, len(array_to_fix) - 1):
		if array_to_fix[k] > array_to_fix[k - 1] and array_to_fix[k] > array_to_fix[k + 1]:
			array_to_fix[k + 1] = array_to_fix[k]
			if k + 2 < len(array_to_fix):
				array_to_fix[k + 1] = max(array_to_fix[k + 1], array_to_fix[k + 2])
			min_oper = min_oper + 1
	print(min_oper)
	print(str(array_to_fix)[1:-1].replace(',', ''))
	min_oper = 0


t = int(input())
for test_case in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	assert len(a) == n
	tally = 0
	for i in range(1, n - 2):
		left = a[i - 1]
		right = a[i + 1]
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			tally += 1
			a[i + 1] = max(a[i], a[i + 2])
	if n > 2:
		if a[n - 2] > a[n - 3] and a[n - 2] > a[n - 1]:
			tally += 1
			a[n - 2] = max(a[n - 3], a[n - 1])
	print(tally)
	print(' '.join(map(str, a)))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	operation = 0
	for i in range(1, len(a) - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			try:
				a[i + 1] = max(a[i], a[i + 2])
			except:
				a[i + 1] = a[i]
			operation += 1
	print(operation)
	a = [str(i) for i in a]
	print(' '.join(a))


t = int(input())

def check_is_local_max(a, j):
	if a[j - 1] < a[j] and a[j] > a[j + 1]:
		return True
	return False

def check_is_local_min(a, j):
	if a[j - 1] > a[j] and a[j] < a[j + 1]:
		return True
	return False
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(1, n - 1):
		if check_is_local_max(a, j):
			if j < n - 2:
				if check_is_local_min(a, j + 1):
					a[j + 1] = max(a[j], a[j + 2])
					count += 1
					continue
			a[j] = max(a[j - 1], a[j + 1])
			count += 1
	print(count)
	print(' '.join((str(e) for e in a)))


for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print
	lst = list(map(int, input().split()))
	ans = 0
	f = 0
	i = 1
	if len(lst) <= 2:
		print(0)
		s = ' '.join([str(i) for i in lst])
		print(s)
	else:
		while i > 0 and i < n - 1:
			if lst[i] > lst[i - 1] and lst[i] > lst[i + 1]:
				if f != 0:
					f = 0
					lst[i - 1] = lst[i]
					i = i + 1
				else:
					f = 1
					ans += 1
					lst[i + 1] = lst[i]
					i = i + 2
			else:
				f = 0
				i = i + 1
		print(ans)
		s = ' '.join([str(i) for i in lst])
		print(s)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.append(0)
	count = 0
	for i in range(1, n - 1):
		if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
			nums[i + 1] = max(nums[i], nums[i + 2])
			count += 1
	print(count)
	for i in range(n):
		nums[i] = str(nums[i])
	print(' '.join(nums[:n]))


for _ in range(int(input())):
	input()
	L = list(map(int, input().split()))
	n = 0
	for i in range(1, len(L) - 1):
		if L[i] > max(L[i + 1], L[i - 1]):
			n += 1
			L[i + 1] = L[i]
			if i + 2 < len(L) and L[i + 2] > L[i + 1]:
				L[i + 1] = L[i + 2]
	print(n)
	print(' '.join(map(str, L)))


def solve(a, n):
	result = []
	m = []
	m.append(0)
	for i in range(1, n - 1):
		if a[i - 1] < a[i] > a[i + 1]:
			m.append(1)
		else:
			m.append(0)
	m.append(0)
	count = 0
	for i in range(n - 1):
		if m[i] == 0:
			result.append(a[i])
			continue
		assert (m[i], m[i + 1]) == (1, 0)
		if i + 2 >= n or m[i + 2] == 0:
			a[i + 1] = a[i]
			m[i] = 0
			count += 1
			result.append(a[i])
			continue
		if m[i + 2] == 1:
			a[i + 1] = max(a[i], a[i + 2])
			m[i] = 0
			m[i + 2] = 0
			count += 1
			result.append(a[i])
			continue
	result.append(a[n - 1])
	assert sum(m) == 0
	return (count, result)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(e) for e in input().split()]
	(modified, result) = solve(a, n)
	print(modified)
	print(' '.join(map(str, result)))


class Solution:

	def avoidLocalMax(self, n, arr):
		change_cnt = 0
		for (i, val) in enumerate(arr):
			if i == 0 or i == n - 1:
				continue
			if val > arr[i - 1] and val > arr[i + 1]:
				change_cnt += 1
				arr[i + 1] = int(max(arr[i + 2], arr[i])) if i < n - 2 else arr[i]
		return (change_cnt, arr)
T = int(input())
sol = Solution()
for t in range(T):
	n = int(input())
	a = list()
	line = input()
	a = list(map(lambda x: int(x), list(line.split(' '))))
	(cnt, arr) = sol.avoidLocalMax(n, a)
	print(cnt)
	print(' '.join(list(map(lambda x: str(x), arr))))


import sys
import math
from fractions import Fraction
from decimal import *
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input().strip())
	inp = input().strip()
	arr = [int(x) for x in inp.split(' ')]
	is_max = [0] * n
	ans = 0
	for i in range(1, len(arr) - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			is_max[i] = 1
	i = 1
	while i < n - 1:
		if is_max[i] == 1:
			if i + 2 < n - 1 and is_max[i + 2] == 1:
				arr[i + 1] = max(arr[i], arr[i + 2])
				ans += 1
				i = i + 3
				continue
			else:
				ans += 1
				arr[i] = max(arr[i - 1], arr[i + 1])
		i += 1
	print(ans)
	print(' '.join([str(x) for x in arr]))
	t -= 1


def solve(arr):
	cnt = 0
	for i in range(1, len(arr) - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			if i + 2 < len(arr):
				arr[i + 1] = max(arr[i], arr[i + 2])
			else:
				arr[i + 1] = arr[i]
			cnt += 1
	return cnt

def main():
	t = int(input())
	arrs = []
	res = []
	for _ in range(t):
		n = input()
		arr = list(map(int, input().split()))
		res.append(solve(arr))
		arrs.append(arr)
	for i in range(t):
		print(res[i])
		print(*arrs[i])
main()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(1, n - 1):
		if a[i] > a[i + 1] and a[i] > a[i - 1]:
			if i + 2 < n:
				a[i + 1] = max(a[i], a[i + 2])
			else:
				a[i + 1] = a[i]
			count += 1
	print(count)
	print(*a)
tst = int(input())
for i in range(tst):
	solve()


k = int(input())
for i in range(k):
	l = int(input()) - 2
	b = [int(x) for x in input().split(' ')]
	if l <= 0:
		print('0')
		print(' '.join([str(x) for x in b]))
		continue
	z = 0
	for j in range(2):
		d = len(b) - 1
		p = b[0]
		for i in range(1, d):
			n = b[i + 1]
			c = b[i]
			if c > p and c > n:
				if i == d - 1:
					b[i + 1] = c
				else:
					nn = b[i + 2]
					b[i + 1] = max(c, nn)
				z += 1
			p = b[i]
	print(str(z))
	print(' '.join([str(x) for x in b]))


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])

def solve(__=1):
	for _ in range(__):
		n = inp()
		a = li()
		c = 0
		for i in range(1, n - 1):
			if a[i] > a[i + 1] and a[i] > a[i - 1]:
				a[i + 1] = max(a[i], a[(i + 2) % n])
				c += 1
		print(c)
		print(*a)
solve(inp())


def fun():
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	change = set()
	for i in range(1, n - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			if i - 1 in change:
				arr[i - 1] = arr[i]
			else:
				arr[i + 1] = arr[i]
				res += 1
				change.add(i + 1)
	print(res)
	return arr
for _ in range(int(input())):
	print(*fun())


import sys

def main():
	a = int(sys.stdin.readline())
	for _ in range(a):
		f = int(sys.stdin.readline())
		x = list(map(int, sys.stdin.readline().split()))
		cnt = 0
		for i in range(1, f - 1):
			if x[i] > x[i - 1] and x[i] > x[i + 1]:
				if i + 3 < f and x[i + 2] > x[i + 1] and (x[i + 2] > x[i + 3]):
					x[i + 1] = max([x[i], x[i + 2]])
					cnt += 1
				else:
					x[i] = max([x[i - 1], x[i + 1]])
					cnt += 1
		print(cnt)
		print(*x)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	for i in range(1, n - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			if i != n - 2 and arr[i + 2] > arr[i]:
				arr[i + 1] = arr[i + 2]
			else:
				arr[i + 1] = arr[i]
			c += 1
	print(c)
	print(*arr)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i + 2 < n:
				a[i + 1] = max(a[i], a[i + 2])
			else:
				a[i + 1] = a[i]
			ans += 1
	print(ans)
	print(*a)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ops = 0
	for j in range(1, n - 1):
		if a[j] > a[j - 1] and a[j] > a[j + 1]:
			ops += 1
			if j + 2 < n:
				a[j + 1] = max(a[j], a[j + 2])
			else:
				a[j + 1] = a[j]
	print(ops)
	print(*a)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = list(l)
	c = 0
	for j in range(1, n - 1):
		if l[j] > l[j - 1] and l[j] > l[j + 1]:
			if l[j - 1] != k[j - 1]:
				l[j - 1] = l[j]
			else:
				c += 1
				l[j + 1] = l[j]
	print(c)
	print(*l)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split())) + [0]
	count = 0
	for i in range(1, n - 1):
		if a[i - 1] < a[i] > a[i + 1]:
			a[i + 1] = max(a[i], a[i + 2])
			count += 1
	print(count)
	print(*a[:-1])


import sys
import math

def cal(a):
	cnt = 0
	for i in range(1, len(a) - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			cnt += 1
			if i + 2 < len(a):
				a[i + 1] = max(a[i], a[i + 2])
			else:
				a[i + 1] = a[i]
	return (cnt, a)
ttime = int(input())
for ccount in range(ttime):
	n = int(input())
	a = list(map(int, input().split()))
	ans = cal(a)
	print(ans[0])
	print(*ans[1])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i < n - 2:
				if a[i] > a[i + 2]:
					a[i + 1] = a[i]
				else:
					a[i + 1] = a[i + 2]
			else:
				a[i + 1] = a[i]
			count += 1
	print(count)
	print(*a)


import sys
input = sys.stdin.readline

def solve(n, arr):
	ops = 0
	i = 1
	while i < n - 1:
		if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
			arr[i + 1] = arr[i] if i == n - 2 else max(arr[i], arr[i + 2])
			ops += 1
		i += 1
	print(ops)
	print(*arr)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(n, arr)


def solve(n, nums):
	ans = 0
	for i in range(1, n - 1):
		if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
			if i + 2 < n:
				nums[i + 1] = max(nums[i], nums[i + 2])
			else:
				nums[i + 1] = nums[i]
			ans += 1
	print(ans)
	print(*nums)
t = int(input())
while t:
	n = int(input())
	nums = list(map(int, input().split()))
	solve(n, nums)
	t -= 1


def solve(n, a):
	if n == 2:
		return 0
	res = 0
	i = 1
	while i < n - 1:
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			res += 1
			a[i + 1] = max(a[i:i + 3])
			i += 2
		else:
			i += 1
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))
	print(*a, sep=' ')


def answer():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		c1(arr, n)

def c1(arr, sz):
	ans = 0
	for j in range(1, sz - 1):
		p = arr[j - 1]
		c = arr[j]
		n = arr[j + 1]
		if c > p and c > n:
			ans = ans + 1
			if j < sz - 2:
				arr[j + 1] = max(c, arr[j + 2])
			else:
				arr[j + 1] = c
	print(ans)
	print(*arr)
answer()


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce
import sys
import decimal

def readIntLine():
	return [int(char) for char in input().split()]

def readCharLine():
	return [char for char in input().split()]

def solve():
	n = int(input())
	arr = readIntLine()
	cnt = 0
	for i in range(1, n - 1):
		(prev, cur, nex) = (arr[i - 1], arr[i], arr[i + 1])
		if prev < cur and cur > nex:
			cnt += 1
			if i + 2 == n or arr[i + 2] <= arr[i]:
				arr[i + 1] = arr[i]
			else:
				arr[i + 1] = arr[i + 2]
	print(cnt)
	print(*arr)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split(' '))))
	c = 0
	for i in range(1, N - 1):
		if A[i] > A[i - 1] and A[i] > A[i + 1]:
			if i + 2 < N:
				A[i + 1] = max(A[i], A[i + 2])
			else:
				A[i + 1] = A[i]
			c += 1
	print(c)
	print(*A)


for _ in range(int(input())):
	(n, l) = (int(input()), list(map(int, input().split())))
	c = 0
	for x in range(1, n - 1):
		if l[x] > l[x - 1] and l[x] > l[x + 1]:
			if x + 2 < n and l[x + 2] >= l[x]:
				l[x + 1] = l[x + 2]
			else:
				l[x + 1] = l[x]
			c += 1
	print(c)
	print(*l)


for _ in range(int(input())):
	length = int(input())
	myList = [int(i) for i in input().split()]
	if length < 3:
		print(0)
		print(*myList)
		continue
	counter = 0
	for i in range(1, length - 2):
		if myList[i - 1] < myList[i] > myList[i + 1]:
			myList[i + 1] = max(myList[i], myList[i + 2])
			counter += 1
	if myList[-3] < myList[-2] > myList[-1]:
		counter += 1
		myList[-2] = max(myList[-1], myList[-3])
	print(counter)
	print(*myList)


def solve(arr):
	changes_count = 0
	for i in range(1, len(arr) - 1):
		if arr[i - 1] < arr[i] and arr[i] > arr[i + 1]:
			changes_count += 1
			if i + 2 >= len(arr):
				arr[i + 1] = arr[i]
			else:
				arr[i + 1] = max(arr[i], arr[i + 2])
	print(changes_count)
	for element in arr:
		print(element, end=' ')
	print()
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr)


a = int(input())
for i in range(a):
	b = int(input())
	A = list(map(int, input().split()))
	j = 0
	for i in range(1, b - 2):
		if A[i - 1] < A[i] > A[i + 1]:
			j += 1
			A[i + 1] = max(A[i], A[i + 2])
	if b > 2:
		if A[-3] < A[-2] > A[-1]:
			j += 1
			A[-2] = max(A[-1], A[-3])
	print(j)
	print(*A)


import sys
import math
from collections import deque, defaultdict
input = sys.stdin.readline

def multiple():
	a = map(int, input().split())
	return a

def array():
	a = input().split()
	return a

def intarray():
	a = list(map(int, input().split()))
	return a

def solution():
	n = int(input())
	s = intarray()
	maxima = [0] * n
	for i in range(1, n - 1):
		if s[i] > s[i - 1] and s[i] > s[i + 1]:
			maxima[i] = 1
	i = 1
	m = 0
	while i < n - 1:
		if maxima[i] == 1:
			if i + 2 < n and maxima[i + 2] == 1:
				s[i + 1] = max(s[i], s[i + 2])
				i += 3
				m += 1
			else:
				s[i] = max(s[i - 1], s[i + 1])
				m += 1
				i += 1
		else:
			i += 1
	print(m)
	print(*s)
t = int(input())
for _ in range(t):
	solution()


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			a[i + 1] = max(a[i], a[(i + 2) % n])
			ans += 1
	print(ans)
	print(*a)
t = int(input())
for _ in range(t):
	solve()


for i in range(int(input())):
	lenn = int(input())
	list1 = list(map(int, input().split()))
	count = 0
	for i in range(1, lenn - 1):
		if list1[i] > list1[i - 1] and list1[i] > list1[i + 1]:
			try:
				if list1[i] < list1[i + 2]:
					list1[i + 1] = list1[i + 2]
				else:
					list1[i + 1] = list1[i]
				count += 1
			except:
				list1[i + 1] = list1[i]
				count += 1
	print(count)
	print(*list1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	local_min = []
	local_max = []
	min_l = 0
	max_l = 0
	for i in range(1, n - 1):
		if l[i - 1] < l[i] and l[i] > l[i + 1]:
			local_max.append(i)
			max_l += 1
			if i + 2 < n:
				l[i + 1] = max(l[i], l[i + 2])
			else:
				l[i + 1] = l[i]
	print(max_l)
	print(*l)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.append(0)
	ctr = 0
	for i in range(1, len(l) - 2):
		if l[i] > l[i - 1] and l[i] > l[i + 1]:
			l[i + 1] = max(l[i], l[i + 2])
			ctr += 1
	print(ctr)
	l = l[:len(l) - 1]
	print(*l)


for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	l = []
	max_y = max(y)
	a = 0
	z = 3
	for i in range(0, x - 2):
		if y[i] < y[i + 1] > y[i + 2]:
			if x - (i + 2) >= 2:
				y[i + 2] = max(y[i + 1], y[i + z])
				a += 1
			else:
				y[i + 2] = y[i + 1]
				a += 1
	print(a)
	print(*y)


for t in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	ans = 0
	for i in range(1, n - 1):
		if A[i] > A[i - 1] and A[i] > A[i + 1]:
			if i + 2 < n:
				A[i + 1] = max(A[i], A[i + 2])
			else:
				A[i + 1] = A[i]
			ans += 1
	print(ans)
	print(*A)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	cntLeft = 0
	cntRight = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i + 2 < n and a[i + 2] >= a[i]:
				a[i + 1] = a[i + 2]
			else:
				a[i + 1] = a[i]
			cntLeft += 1
	for i in range(n - 2, 0):
		if b[i] > b[i + 1] and b[i] > b[i - 1]:
			if i - 2 >= 0 and b[i - 2] >= b[i]:
				b[i - 1] = b[i - 2]
			else:
				b[i - 1] = b[i]
			cntRight += 1
	if cntRight < cntLeft:
		print(cntLeft)
		print(*a)
	else:
		print(cntRight)
		print(*b)


mod = 10000000
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i + 2 < n:
				a[i + 1] = max(a[i], a[i + 2])
			else:
				a[i + 1] = a[i]
			c += 1
	print(c)
	print(*a)


for _ in range(int(input())):
	n = int(input())
	k = [int(i) for i in input().split()]
	k = [k[0] + 1] + k + [k[-1] + 1]
	d = 0
	for i in range(1, n):
		if k[i] > k[i + 1] and k[i] > k[i - 1]:
			k[i + 1] = max(k[i], k[i + 2])
			d += 1
	print(d)
	print(*k[1:-1])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(XXX) for XXX in input().split()]
	res = 0
	for i in range(1, n - 1):
		if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
			arr[i + 1] = max(arr[i], arr[i + 2]) if i + 2 < n else arr[i]
			res += 1
	print(res)
	print(*arr, sep=' ')


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	(l, m) = (-10000000000.0, 10000000000.0 + 1)
	ans = 0
	for i in range(n):
		if m > l and m > s[i] and (m != 10000000000.0 + 1):
			if i != n - 1:
				s[i] = max(m, s[i + 1])
			else:
				s[i] = m
			ans += 1
		(l, m) = (m, s[i])
	print(ans)
	print(*s)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.append(0)
	opr = 0
	for i in range(1, len(a) - 2):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			opr += 1
			a[i + 1] = max(a[i], a[i + 2])
	print(opr)
	a = a[:len(a) - 1]
	print(*a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	max_m = max(a)
	for i in range(1, n - 1):
		if a[i - 1] < a[i] > a[i + 1]:
			a[i + 1] = a[i] if i + 2 >= n else max(a[i], a[i + 2])
			k += 1
	print(k)
	print(*a)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	i = 1
	for i in range(1, n - 1):
		if a[i] > a[i - 1] and a[i] > a[i + 1]:
			if i + 2 < n:
				a[i + 1] = max(a[i], a[i + 2])
			else:
				a[i + 1] = a[i]
			cnt += 1
	print(cnt)
	for x in a:
		print(x, end=' ')
	print()
t = int(input())
while t:
	solve()
	t -= 1


for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()] + [0]
	if n == 2:
		print(0)
		print(*arr[:n])
	else:
		ct = 0
		for i in range(1, n - 1):
			if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
				arr[i + 1] = max(arr[i], arr[i + 2])
				ct += 1
		print(ct)
		print(*arr[:n])