You are given a sequence $a$ of length $n$ consisting of $0$s and $1$s.

You can perform the following operation on this sequence:

Pick an index $i$ from $1$ to $n-2$ (inclusive).

Change all of $a_{i}$, $a_{i+1}$, $a_{i+2}$ to $a_{i} \oplus a_{i+1} \oplus a_{i+2}$ simultaneously, where $\oplus$ denotes the bitwise XOR operation Find a sequence of at most $n$ operations that changes all elements of $a$ to $0$s or report that it's impossible.

We can prove that if there exists a sequence of operations of any length that changes all elements of $a$ to $0$s, then there is also such a sequence of length not greater than $n$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

The first line of each test case contains a single integer $n$ ($3 \le n \le 2\cdot10^5$) — the length of $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = 0$ or $a_i = 1$) — elements of $a$.

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


-----Output-----

For each test case, do the following:

if there is no way of making all the elements of $a$ equal to $0$ after performing the above operation some number of times, print "NO".

otherwise, in the first line print "YES", in the second line print $k$ ($0 \le k \le n$) — the number of operations that you want to perform on $a$, and in the third line print a sequence $b_1, b_2, \dots, b_k$ ($1 \le b_i \le n - 2$) — the indices on which the operation should be applied.

If there are multiple solutions, you may print any.


-----Examples-----

Input
3
3
0 0 0
5
1 1 1 1 0
4
1 0 0 1
Output
YES
0
YES
2
3 1
NO


-----Note-----

In the first example, the sequence contains only $0$s so we don't need to change anything.

In the second example, we can transform $[1, 1, 1, 1, 0]$ to $[1, 1, 0, 0, 0]$ and then to $[0, 0, 0, 0, 0]$ by performing the operation on the third element of $a$ and then on the first element of $a$.

In the third example, no matter whether we first perform the operation on the first or on the second element of $a$ we will get $[1, 1, 1, 1]$, which cannot be transformed to $[0, 0, 0, 0]$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Greedy algorithms

Complete search

Amortized analysis

Constructive algorithms


Solutions:
import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())
add = lambda x: x + 1

def f(n, a):
	m = f = 1
	c = g = 0
	x = n
	xc = 0
	z = []
	for i in range(n):
		if a[i] == m:
			c += 1
		elif m == 1:
			if c & 1 == 0:
				for j in range(c // 2):
					z.append(i - 2 * j - 2)
				if f:
					f = g = 0
			else:
				g = 1
				x = i
				xc = c
			c = 1
		elif g:
			if c & 1 == 0:
				if f:
					for j in range(x - 1, i - 2, 2):
						z.append(j)
					c = i + 1
				else:
					for j in range(x - xc - 1, x - 3, 2):
						z.append(j)
					for j in range(x - 2, i - 3, 2):
						z.append(j)
					z.append(i - 2)
					for j in range(i - 4, x - 3, -2):
						z.append(j)
					c = g = 0
			else:
				if f:
					f = 0
				for j in range(x - 1, i - 3, 2):
					z.append(j)
				z.append(i - 2)
				for j in range(i - 4, x - 2, -2):
					z.append(j)
				for j in range(x - 3, x - xc - 1, -2):
					z.append(j)
				c = g = 0
		else:
			if f:
				f = 0
			c = 1
		m = a[i]
	if g or (m and (c & 1 or c == n)):
		return (0, [])
	if m:
		for j in range(n - c - 1, n - 2, 2):
			z.append(j)
	return (1, z)
O = []
for _ in range(int(Z())):
	(b, z) = f(int(Z()), [*Y()])
	if b:
		O.append('YES')
		O.append(str(len(z)))
		if z:
			O.append(' '.join(map(str, map(add, z))))
	else:
		O.append('NO')
print('\n'.join(O))


import collections
import math
import itertools
import sys
import time
import random

def fast_input():
	return sys.stdin.readline().strip()
input = fast_input

def ints_input():
	return list((int(x) for x in input().split()))

def int_input():
	return int(input())

def solve():
	n = int_input()
	a = ints_input()
	if sum(a) % 2 == 1:
		print('NO')
		return
	reversed = False
	ops = []

	def do_op(i):
		ops.append(i + 1)
		a[i] = a[i + 1] = a[i + 2] = a[i] ^ a[i + 1] ^ a[i + 2]
	if a[0] == 1:
		i = 1
		found = False
		while i + 1 < n:
			if a[i] == a[i + 1]:
				i += 2
			else:
				found = True
				break
		if not found:
			if i == n - 1 and a[i] == 1:
				print('NO')
				return
			else:
				reversed = True
				a = a[::-1]
				if a[0] == 1:
					do_op(0)
		else:
			x = i
			while x >= 1:
				do_op(x - 1)
				x -= 2
	p = 1
	while p + 1 < n:
		if a[p] != a[p + 1]:
			do_op(p)
			if a[p] == 0:
				p += 2
		else:
			if a[p] != 0:
				do_op(p - 1)
			p += 2
	print('YES')
	print(len(ops))
	if reversed:
		ops = [n - 1 - i for i in ops]
	print(' '.join([str(x) for x in ops]))
if True:
	for _ in range(int_input()):
		solve()
else:
	solve()


import sys
import getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

def solve_(arr):
	if sum(arr) == 0:
		return []
	if arr.count(0) == 0:
		return -1
	if sum(arr) % 2 == 1:
		return -1
	left_ones = 0
	res = []
	for i in range(len(arr)):
		x = arr[i]
		log(i, x, left_ones)
		if x == 0:
			if left_ones == 0:
				continue
			if left_ones % 2 == 0:
				j = i - 2
				while j >= 0 and arr[j] == 1:
					assert arr[j] == 1
					assert arr[j + 1] == 1
					assert arr[j + 2] == 0
					(arr[j], arr[j + 1], arr[j + 2]) = (0, 0, 0)
					res.append(j)
					log(arr)
					j -= 2
			else:
				if i + 1 == len(arr):
					return -1
				if arr[i + 1] != 1:
					if i > 0 and arr[i - 1] == 1:
						assert arr[i - 1] == 1
						assert arr[i] == 0
						assert arr[i + 1] == 0
						(arr[i - 1], arr[i], arr[i + 1]) = (1, 1, 1)
						log(arr)
						res.append(i - 1)
						left_ones += 1
						continue
				assert arr[i - 1] == 1
				assert arr[i] == 0
				assert arr[i + 1] == 1
				(arr[i - 1], arr[i], arr[i + 1]) = (0, 0, 0)
				log(arr)
				res.append(i - 1)
				j = i - 3
				while j >= 0 and arr[j] == 1:
					assert arr[j] == 1
					assert arr[j + 1] == 1
					assert arr[j + 2] == 0
					(arr[j], arr[j + 1], arr[j + 2]) = (0, 0, 0)
					res.append(j)
					log(arr)
					j -= 2
			left_ones = 0
		else:
			left_ones += 1
	log(arr)
	sumarr = sum(arr)
	if sumarr == 0:
		return res
	if arr.count(0) == 0:
		return -1
	if sumarr % 2 == 1:
		return -1
	assert arr[0] == 0
	for i in range(len(arr)):
		if arr[i] == 1:
			assert arr[i - 1] == 0
			assert arr[i] == 1
			assert arr[i + 1] == 1
			(arr[i - 1], arr[i], arr[i + 1]) = (0, 0, 0)
			log(arr)
			res.append(i - 1)
	assert sum(arr) == 0
	return res
for case_num in range(int(input())):
	k = int(input())
	lst = list(map(int, input().split()))
	res = solve([x for x in lst])
	assert (res == -1) == (solve(lst[::-1]) == -1)
	if res == -1:
		print('NO')
		continue
	print('YES')
	print(len(res))
	res = ' '.join((str(x + 1) for x in res))
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	r = 0
	mid = -1
	for (i, c) in enumerate(arr):
		r ^= c
		if r == 0 and i % 2 == 0:
			mid = i
	if r:
		print('NO')
	elif n % 2 == 1:
		print('YES')
		ans = []
		ans.extend(list(range(1, n - 1, 2)))
		ans.extend(list(range(n - 2, 0, -2)))
		print(len(ans))
		print(*ans)
	elif n % 2 == 0:
		if mid == -1:
			print('NO')
		else:
			print('YES')
			ans = []
			ans.extend(list(range(1, mid, 2)))
			ans.extend(list(range(mid - 1, 0, -2)))
			ans.extend(list(range(mid + 2, n - 1, 2)))
			ans.extend(list(range(n - 2, mid + 1, -2)))
			print(len(ans))
			print(*ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	AA = now = 0
	for i in range(n):
		now ^= a[i]
		if not now and (not i % 2):
			AA = i + 1
	if not AA or now:
		print('NO')
	else:
		print('YES')
		an = []
		for i in range(1, AA, 2):
			an.append(str(i))
		for i in range(AA + 1, n - 1, 2):
			an.append(str(i))
		an.extend(an[::-1])
		print(len(an))
		print(' '.join(an))