Tzuyu gave Nayeon a strip of $N$ cells (numbered $1$ through $N$) for her birthday. This strip is described by a sequence $A_1, A_2, \ldots, A_N$, where for each valid $i$, the $i$-th cell is blocked if $A_i = 1$ or free if $A_i = 0$. Tzuyu and Nayeon are going to use it to play a game with the following rules:
- The players alternate turns; Nayeon plays first.
- Initially, both players are outside of the strip. However, note that afterwards during the game, their positions are always different.
- In each turn, the current player should choose a free cell and move there. Afterwards, this cell becomes blocked and the players cannot move to it again.
- If it is the current player's first turn, she may move to any free cell.
- Otherwise, she may only move to one of the left and right adjacent cells, i.e. from a cell $c$, the current player may only move to the cell $c-1$ or $c+1$ (if it is free).
- If a player is unable to move to a free cell during her turn, this player loses the game.
Nayeon and Tzuyu are very smart, so they both play optimally. Since it is Nayeon's birthday, she wants to know if she can beat Tzuyu. Find out who wins.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing the string "Yes" if Nayeon wins the game or "No" if Tzuyu wins (without quotes).

-----Constraints-----
- $1 \le T \le 40,000$
- $2 \le N \le 3\cdot 10^5$
- $0 \le A_i \le 1$ for each valid $i$
- $A_1 = A_N = 1$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (50 points): $A_i = 0$ for each $i$ ($2 \le i \le N-1$)
Subtask #2 (50 points): original constraints

-----Example Input-----
4
7
1 1 0 0 0 1 1
8
1 0 1 1 1 0 0 1
4
1 1 0 1
4
1 1 1 1

-----Example Output-----
Yes
No
Yes
No

-----Explanation-----
Example case 1: Since both Nayeon and Tzuyu play optimally, Nayeon can start e.g. by moving to cell $4$, which then becomes blocked. Tzuyu has to pick either the cell $3$ or the cell $5$, which also becomes blocked. Nayeon is then left with only one empty cell next to cell $4$ (the one Tzuyu did not pick); after she moves there, Tzuyu is unable to move, so she loses the game.
Example case 2: Regardless of what cell Nayeon moves to at the start, Tzuyu will always be able to beat her.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	z = {}
	c = 0
	for i in range(N):
		if A[i] == 0:
			c += 1
		else:
			if c != 0:
				if c in z.keys():
					z[c] += 1
				else:
					z[c] = 1
			c = 0
	if z == {}:
		print('No')
	else:
		z_max = max(z.keys())
		if z[z_max] > 1:
			print('No')
		elif z_max == 1:
			print('Yes')
		elif z_max % 2 == 0:
			print('No')
		else:
			for i in range(z_max // 2 + 1, z_max):
				if i in z.keys():
					print('No')
					break
			else:
				print('Yes')


def stripModified(a):
	for i in a:
		if len(i) == 0:
			a.remove(i)
	return a
t = int(input())
while t > 0:
	n = int(input())
	vals = list(map(int, input().split(' ')))
	modified = ''
	inOneZone = False
	for i in vals:
		if i == 0:
			modified += str(i)
			inOneZone = False
		elif i == 1 and inOneZone == False:
			modified += str(i)
			inOneZone = True
	modified = stripModified(modified.split('1'))
	modified = stripModified(modified)
	zeroZones = len(modified)
	if zeroZones == 0:
		print('No')
	elif zeroZones == 1:
		print('Yes' if len(modified[0]) % 2 != 0 else 'No')
	else:
		l = max(modified, key=len)
		modified.remove(l)
		l2 = max(modified, key=len)
		if len(l) % 2 != 0 and len(l2) < (len(l) + 1) / 2:
			print('Yes')
		else:
			print('No')
	t -= 1


from itertools import groupby
for i in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	q = [(len(list(c)), int(k)) for (k, c) in groupby(l)]
	k = []
	for i in range(0, len(q)):
		if q[i][1] == 0:
			k.append(q[i][0])
	k.sort(reverse=True)
	if len(k) == 0:
		print('No')
	elif len(k) == 1:
		if k[0] % 2 == 1:
			print('Yes')
		else:
			print('No')
	else:
		li = k[0]
		sl = k[1]
		if k[0] % 2 == 1 and sl < (li + 1) // 2:
			print('Yes')
		else:
			print('No')


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	z = 0
	l = []
	for i in k:
		if i == 0:
			z += 1
		else:
			l.append(z)
			z = 0
	l.append(z)
	l.remove(0)
	l.sort()
	if l[-1] == 1:
		if l.count(1) >= 2:
			print('No')
		else:
			print('Yes')
	elif l[-1] <= 2:
		print('No')
	elif l[-1] & 1:
		if len(l) >= 2 and l[-1] // 2 < l[-2]:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def find_2_largest(string):
	(max_one, max_two) = (0, 0)
	count = 0
	for i in string:
		if i == 0:
			count += 1
		else:
			if count > max_one:
				max_two = max_one
				max_one = count
			elif count > max_two:
				max_two = count
			count = 0
	return (max_one, max_two)

def main():
	for _ in tr():
		n = nl()
		strip = ln()
		strip.append(1)
		(max_one, max_two) = find_2_largest(strip)
		if max_one % 2 == 1 and max_two < (max_one + 1) // 2:
			print('Yes')
		else:
			print('No')
main()


t = int(input())
for i in range(t):
	n = int(input())
	strip = input().split()
	countlist = []
	count = 0
	for k in range(n):
		strip[k] = int(strip[k])
		if strip[k] == 0:
			count += 1
		elif strip[k] == 1 and count != 0:
			countlist.append(count)
			count = 0
	length = len(countlist)
	countlist.sort()
	if countlist == []:
		print('No')
	elif length == 1:
		if countlist[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
	elif countlist[-1] % 2 == 1 and (countlist[-1] + 1) / 2 > countlist[-2]:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	even = 0
	zeroes = 0
	nn = []
	for i in range(n):
		if arr[i] == 0:
			zeroes += 1
		else:
			if zeroes != 0:
				nn.append(zeroes)
			zeroes = 0
	nn.sort(reverse=True)
	if len(nn) >= 2:
		if (nn[0] + 1) // 2 <= nn[1]:
			print('No')
		elif nn[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
	elif len(nn) == 1:
		if nn[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


from collections import defaultdict
for t in range(int(input())):
	n = int(input())
	store = list(map(int, input().split()))
	count = 0
	curr = 0
	cStore = defaultdict()
	for i in range(n):
		if store[i] == 0:
			if curr > 0:
				curr += 1
			else:
				curr = 1
		elif curr != 0:
			if curr in cStore:
				cStore[curr] += 1
			else:
				cStore[curr] = 1
			curr = 0
	flag = 0
	maxi = 0
	for val in cStore:
		if cStore[val] > 1:
			flag = 1
			break
		elif val > maxi:
			maxi = val
	if flag == 1:
		print('No')
	elif maxi % 2 == 0:
		print('No')
	else:
		print('Yes')


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
t = ri()
for test in range(t):
	n = ri()
	l = rl()
	i = mx = smx = 0
	cnt = 0
	while i < n:
		if l[i] == 0:
			c = 0
			while i < n and l[i] == 0:
				i += 1
				c += 1
			if mx < c:
				smx = mx
				mx = c
			elif smx < c:
				smx = c
		i += 1
	if mx % 2 and smx < (mx + 1) // 2:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, k) = (int(input()), 0)
	(strips, seg) = (list(map(int, input().split())), [])
	for __ in range(n):
		if strips[__] == 0:
			k += 1
		elif k > 0:
			seg.append(k)
			k = 0
	seg.sort(reverse=True)
	if len(seg) == 0:
		print('No')
	elif len(seg) == 1:
		if seg[0] & 1:
			print('Yes')
		else:
			print('No')
	elif not seg[0] & 1:
		print('No')
	else:
		left = (seg[0] + 1) // 2
		if left <= seg[1]:
			print('No')
		else:
			print('Yes')


def getSecondLarge(s):
	c = 0
	mx = 0
	for i in s:
		if i == 0:
			c += 1
			mx = max(mx, c)
		else:
			mx = max(mx, c)
			c = 0
	return mx
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	c = 0
	mx = 0
	midx = 0
	mx1 = 0
	for i in range(len(ar)):
		if ar[i] == 0:
			c += 1
			if mx < c:
				midx = i
				mx = c
		else:
			if mx < c:
				midx = i
				mx = c
			mx = max(mx, c)
			c = 0
	if mx == 0:
		print('No')
	else:
		t = max(getSecondLarge(ar[:midx - mx + 1]), getSecondLarge(ar[midx + 1:]))
		if mx % 2 != 0 and t < (mx + 1) // 2:
			print('Yes')
		else:
			print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(m1, m2) = (0, 0)
	start = False
	c = 0
	for i in l:
		if not start and i == 0:
			c = 1
			start = True
		elif start and i == 1:
			if c >= m1:
				m2 = m1
				m1 = c
			elif c > m2:
				m2 = c
			c = 0
			start = False
		elif start and i == 0:
			c += 1
	if m1 == 0 and m2 == 0:
		print('No')
		continue
	if m1 % 2 == 1:
		if m2 <= m1 // 2:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


test = int(input())
for _ in range(test):
	n = int(input())
	pos = list(map(int, input().split()))
	r = []
	i = 0
	while i < n:
		if pos[i] == 0:
			c = 0
			while i < n and pos[i] == 0:
				c += 1
				i += 1
			r.append(c)
		i += 1
	r = sorted(r)[::-1]
	if len(r) == 0:
		print('No')
	elif len(r) == 1:
		if r[0] % 2 == 1:
			print('Yes')
		else:
			print('No')
	elif (r[0] + 1) // 2 > r[1] and r[0] % 2 == 1:
		print('Yes')
	else:
		print('No')


def isOne(slen):
	count = 0
	for i in slen:
		if i == 1:
			count += 1
		else:
			return False
	return count == 1

def isOdd(slen):
	for i in slen:
		if i % 2 == 1 and i > 1:
			return True
	else:
		return False
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	slen = []
	i = 0
	while i < N:
		if A[i] == 0:
			e = i
			while e < N and A[e] == 0:
				e += 1
			slen.append(e - i)
			i = e + 1
		else:
			i += 1
	if len(slen) != 0 and (isOne(slen) or isOdd(slen)):
		ans.append('Yes')
	else:
		ans.append('No')
for i in ans:
	print(i)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	longest_set_of_zeroes = 0
	second_longest_zeroes = 0
	subset = 0 if A[0] == 1 else 1
	for i in range(1, N):
		if A[i] == 0:
			subset += 1
		if A[i] == 1 or i == N - 1:
			if subset > longest_set_of_zeroes:
				second_longest_zeroes = longest_set_of_zeroes
				longest_set_of_zeroes = subset
			elif subset > second_longest_zeroes:
				second_longest_zeroes = subset
			subset = 0
	if longest_set_of_zeroes % 2 == 0:
		print('No')
	elif longest_set_of_zeroes // 2 >= second_longest_zeroes:
		print('Yes')
	else:
		print('No')


numb_cases = int(input())
for i in range(0, numb_cases):
	n = int(input())
	data = map(int, input().split())
	count = 0
	max_count = 0
	second_max_count = 0
	flag = False
	for char in data:
		if char == 0:
			count += 1
			flag = True
		elif flag:
			flag = False
			if count > max_count:
				second_max_count = max_count
				max_count = count
			elif count > second_max_count:
				second_max_count = count
			count = 0
	if max_count % 2 == 0:
		print('No')
	elif max_count // 2 < second_max_count:
		print('No')
	else:
		print('Yes')


result = []
groupOfZero = []
counter = 0
t = int(input())
index = 0
while index < t:
	n = int(input())
	temp = list(input().split())
	for i in range(0, len(temp)):
		if temp[i] == '0':
			counter = counter + 1
		else:
			if counter != 0:
				groupOfZero.append(counter)
			counter = 0
		if i == len(temp) - 1 and counter != 0:
			groupOfZero.append(counter)
	groupOfZero.sort()
	groupOfZero.reverse()
	if len(groupOfZero) > 1:
		if groupOfZero[1] > int(groupOfZero[0] / 2):
			result.append('No')
			temp.clear()
			groupOfZero.clear()
			counter = 0
			index = index + 1
			continue
	if len(groupOfZero) == 0:
		result.append('No')
		temp.clear()
		groupOfZero.clear()
		counter = 0
		index = index + 1
		continue
	if int(groupOfZero[0] % 2) != 0:
		result.append('Yes')
	elif int(groupOfZero[0] % 2) == 0:
		result.append('No')
	temp.clear()
	groupOfZero.clear()
	counter = 0
	index = index + 1
for i in range(0, len(result)):
	print(result[i])


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = ''.join([str(ele) for ele in li])
	li = list(s.split('1'))
	ans = []
	for ele in li:
		if ele != '':
			ans.append(ele)
	if len(ans) == 0:
		print('No')
		continue
	for i in range(len(ans)):
		ans[i] = ans[i].count('0')
	if len(ans) == 1:
		if ans[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
		continue
	elif max(ans) % 2 == 0:
		print('No')
	else:
		d = max(ans)
		ans.remove(max(ans))
		if d // 2 + 1 > max(ans):
			print('Yes')
		else:
			print('No')


def longest_substring(s, k):
	n = len(s)
	if k > 1:
		s += s
		n *= 2
	ans = 0
	i = 0
	while i < n:
		x = 0
		while i < n and s[i] == '0':
			(x, i) = (x + 1, i + 1)
		ans = max(ans, x)
		i += 1
	if k == 1 or ans != n:
		return ans
	else:
		return ans // 2 * k
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	s = ''
	for u in lst:
		s += str(u)
	m1 = longest_substring(s, 1)
	if m1 == 0:
		print('No')
	else:
		ind = s.index('0' * m1)
		lstf = list(s)
		for r in range(ind, ind + m1):
			lstf[r] = ''
		s = ''
		for b in lstf:
			s += str(b)
		m2 = longest_substring(s, 1)
		if m2 == 0:
			if m1 % 2 == 0:
				print('No')
			else:
				print('Yes')
		elif m1 % 2 != 0 and m2 < (m1 + 1) // 2:
			print('Yes')
		else:
			print('No')


t = int(input())
while t:
	n = int(input())
	ls = [int(i) for i in input().split(' ')]
	if ls.count(0) == 0:
		print('No')
		t -= 1
		continue
	prev = -1
	ans = []
	for i in range(n):
		if ls[i] == 0 and prev == -1:
			prev = i
		if ls[i] == 1 and prev != -1:
			ans.append(i - prev)
			prev = -1
	if prev != -1:
		ans.append(n - prev)
	(val, count) = (max(ans) // 2 + max(ans) % 2, 0)
	for i in range(len(ans)):
		if ans[i] >= val:
			count += 1
	if count == 1 and max(ans) % 2 != 0:
		print('Yes')
	else:
		print('No')
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	l = []
	c = 0
	for j in range(n):
		s[j] = int(s[j])
		if s[j] == 0:
			c += 1
		elif s[j] == 1 and c != 0:
			l.append(c)
			c = 0
	r = len(l)
	l.sort()
	if l == []:
		print('No')
	elif r == 1:
		if l[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
	elif l[-1] % 2 == 1 and (l[-1] + 1) / 2 > l[-2]:
		print('Yes')
	else:
		print('No')


test_case = int(input())
while test_case > 0:
	test_case -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	c = list()
	temp = 0
	times = 0
	flag = True
	for a in arr:
		if a == 0:
			temp += 1
			if flag:
				flag = False
				times += 1
		else:
			c.append(temp)
			temp = 0
			flag = True
	c.append(temp)
	max1 = max(c)
	c.remove(max1)
	max2 = max(c)
	if max1 % 2 == 0 or max1 / 2 + (max1 & 1) <= max2:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	fmax = smax = count = 0
	for i in range(n):
		if l[i] == 1:
			if count != 0:
				if count > fmax:
					smax = fmax
					fmax = count
				elif count > smax:
					smax = count
				count = 0
		else:
			count += 1
	if fmax % 2 != 0 and smax < (fmax + 1) // 2:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	input()
	big = med = cur = 0
	for b in input().split():
		if b == '1':
			if cur > big:
				med = big
				big = cur
			elif cur > med:
				med = cur
			cur = 0
		else:
			cur += 1
	print('Yes' if big & 1 and med <= big >> 1 else 'No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	Fmax = Smax = count = 0
	for i in range(n):
		if a[i] == 1:
			if count != 0:
				if count > Fmax:
					Smax = Fmax
					Fmax = count
				elif count > Smax:
					Smax = count
				count = 0
		else:
			count += 1
	if Fmax % 2 != 0 and Smax < (Fmax + 1) // 2:
		print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	(r, i) = ([], 0)
	while i < n:
		if l[i] == 0:
			c = 0
			while i < n and l[i] == 0:
				c += 1
				i += 1
			r.append(c)
		i += 1
	r = sorted(r)[::-1]
	if len(r) == 0:
		print('No')
	elif len(r) == 1:
		if r[0] % 2 == 1:
			print('Yes')
		else:
			print('No')
	elif (r[0] + 1) // 2 > r[1] and r[0] % 2 == 1:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	l = []
	c = 0
	for i in s:
		if i == 1:
			l.append(c)
			c = 0
		else:
			c += 1
	if c:
		l.append(c)
	l.sort()
	if not l:
		print('No')
	elif len(l) == 1:
		if l[0] % 2 == 1:
			print('Yes')
		else:
			print('No')
	elif l[-1] // 2 + 1 > l[-2] and l[-1] % 2:
		print('Yes')
	else:
		print('No')


t = int(input())
while t > 0:
	n = int(input())
	str1 = str(input()).split(' ')
	str1 = list(map(int, str1))
	output = 'No'
	totalCount = 0
	count = 0
	for i in str1:
		if i == 0:
			count += 1
			totalCount += 1
		elif i == 1 and count > 0:
			if count % 2 == 1 and totalCount != 1:
				output = 'Yes'
				break
			count = 0
	if str1[-1] == 0 and count % 2 == 1 and (totalCount != 1):
		output = 'Yes'
	if totalCount == 1:
		output = 'Yes'
	print(output)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input().split()
	s = ''.join(s).split('1')
	l = []
	for i in s:
		if len(i) == 0:
			continue
		else:
			l.append(i)
	l.sort(reverse=True, key=len)
	if len(l) == 0:
		print('No')
	elif len(l) == 1:
		if len(l[0]) % 2 == 0:
			print('No')
		else:
			print('Yes')
	else:
		(m1, m2) = (len(l[0]), len(l[1]))
		if m1 % 2 == 0:
			print('No')
		elif m1 % 2 and (m1 + 1) / 2 > m2:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	(one, two) = (int(), int())
	n = int(input())
	lis = list(map(int, input().split()))
	cnt = 0
	for i in lis:
		if i == 0:
			cnt += 1
		else:
			if cnt > one:
				two = one
				one = cnt
			elif cnt > two:
				two = cnt
			cnt = 0
	if one % 2 and two < (one + 1) // 2:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	zeros = []
	if 0 not in a:
		print('No')
	elif a.count(0) == 1:
		print('Yes')
		continue
	else:
		i = 0
		while i < n:
			x = i
			while i < n and a[i] == 0:
				i += 1
			zeros.append(i - x)
			i += 1
		zeros.sort()
		maxcount = max(zeros)
		zeros.remove(maxcount)
		nextmax = max(zeros)
		if maxcount & 1 and nextmax < (maxcount + 1) / 2:
			print('Yes')
		else:
			print('No')


for i in range(int(input())):
	n = input()
	arr = list(map(int, input().split()))
	fMax = sMax = count = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			if count != 0:
				if count > fMax:
					sMax = fMax
					fMax = count
				elif count > sMax:
					sMax = count
				count = 0
		else:
			count += 1
	if fMax % 2 != 0 and (fMax + 1) / 2 > sMax:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def find_path_lengths(n, a):
	(temp, path_lengths) = (0, [])
	for i in range(n):
		if a[i] == 0:
			temp += 1
		if temp and i != n - 1 and (a[i + 1] == 1):
			path_lengths += [temp]
			temp = 0
	if temp:
		path_lengths += [temp]
	return sorted(path_lengths, reverse=True)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	path_lengths = find_path_lengths(n, a)
	size = len(path_lengths)
	if size == 0 or (size == 1 and path_lengths[0] % 2 == 0):
		print('No')
	elif size == 1 and path_lengths[0] % 2 == 1:
		print('Yes')
	elif path_lengths[0] % 2 == 0:
		print('No')
	elif (path_lengths[0] + 1) // 2 > path_lengths[1]:
		print('Yes')
	else:
		print('No')


from collections import defaultdict
import math
for t in range(int(input())):
	n = int(input())
	store = list(map(int, input().split()))
	count = 0
	curr = 0
	cStore = defaultdict()
	maxi = 0
	second = 0
	for i in range(n):
		if store[i] == 0:
			if curr > 0:
				curr += 1
			else:
				curr = 1
		else:
			if curr > maxi:
				second = maxi
				maxi = curr
			elif curr > second:
				second = curr
			curr = 0
	if second != 0 and math.ceil(maxi / 2) < second:
		print('No')
	elif maxi % 2 == 0:
		print('No')
	else:
		print('Yes')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	long = 0
	prev = 0
	cur = 0
	for i in a:
		if i == 0:
			cur += 1
		else:
			if cur == 0:
				continue
			if cur > long:
				prev = long
				long = cur
			elif cur > prev:
				prev = cur
			cur = 0
	if long & 1 and prev < (long + 1) // 2:
		print('Yes')
	else:
		print('No')


def bestSecond(A, n):
	best = 0
	second = 0
	counter = 0
	for i in range(n):
		if A[i] == 0:
			counter += 1
		else:
			if counter > best:
				second = best
				best = counter
			elif counter == best:
				second = counter
			elif counter > second:
				second = counter
			counter = 0
	return (best, second)
T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	(best, second) = bestSecond(A, n)
	eh = 0
	if best % 2 == 0:
		eh = best / 2
	else:
		eh = 1 + best // 2
	if best == second == 0:
		print('No')
	elif second >= eh:
		print('No')
	elif best % 2 == 0:
		print('No')
	else:
		print('Yes')


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(int)
	cnt = 0
	for ele in arr:
		if ele == 1:
			if cnt > 0:
				d[cnt] += 1
			cnt = 0
		else:
			cnt += 1
	if cnt > 0:
		d[cnt] += 1
	if len(d.keys()) == 0:
		print('No')
		continue
	(mx, smax) = (-1, -1)
	for k in d.keys():
		if k > mx:
			(smax, mx) = (mx, k)
		elif k > smax:
			smax = k
	if mx % 2 == 1:
		if d[mx] > 1 or smax >= mx // 2 + 1:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	leo = [0]
	c = 0
	for i in range(n):
		if l[i] == 0:
			c = c + 1
		elif c != 0:
			leo.append(c)
			c = 0
	a = max(leo)
	leo.remove(a)
	if a % 2 == 0:
		print('No')
	else:
		b = max(leo)
		if (a + 1) // 2 > b:
			print('Yes')
		else:
			print('No')


for t in range(int(input())):
	n = int(input())
	a = list(input().split())
	highest = 0
	current = 0
	second = 0
	for i in a:
		if i == '0':
			current += 1
		elif current != 0:
			if current > highest:
				second = highest
				highest = current
			elif current > second:
				second = current
			current = 0
	else:
		if current != 0:
			if current > highest:
				second = highest
				highest = current
			elif current > second:
				second = current
	if highest % 2 != 0 and highest > second * 2:
		print('Yes')
	else:
		print('No')


def rin():
	return list(map(int, input().split()))
for _ in range(int(input())):
	N = int(input())
	A = rin()
	c = int(A[0] == 0)
	freq = []
	for i in range(1, N):
		if A[i] == 0:
			c += 1
		else:
			freq.append(c)
			c = 0
	freq.append(c)
	freq.sort(reverse=True)
	if freq[1] < (freq[0] + 1) // 2 and freq[0] & 1:
		print('Yes')
	else:
		print('No')


test_case = int(input())
while test_case > 0:
	test_case -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	c = 0
	temp = 0
	times = 0
	flag = True
	for a in arr:
		if a == 0:
			temp += 1
			if flag:
				flag = False
				times += 1
		else:
			c = max(c, temp)
			temp = 0
			flag = True
	if c % 2 == 0:
		print('No')
	else:
		print('Yes')


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(i, j) = (0, 0)
	x = []
	while i < n and j < n:
		if a[i] == 0:
			while j < n and a[j] == 0:
				j += 1
			x.append(j - i)
			i = j
		else:
			i += 1
			j = i
	if len(x) == 0:
		print('No')
		continue
	elif len(x) == 1:
		if x[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
		continue
	x.sort()
	if x[-1] == x[-2]:
		print('No')
		continue
	elif x[-1] % 2 == 0:
		print('No')
	elif x[-1] // 2 < x[-2]:
		print('No')
	else:
		print('Yes')


for i in range(int(input())):
	int(input())
	a = [int(x) for x in input().split()]
	a = ''.join(map(str, a))
	c = []
	count = 0
	for i in a:
		if i == '0':
			count = count + 1
		if i == '1':
			if count != 0:
				c.append(count)
				count = 0
	c.sort()
	if len(c) > 1:
		u = (c[-1] + 1) // 2
		if c[-1] % 2 != 0 and u > c[-2]:
			print('Yes')
		else:
			print('No')
	elif len(c) == 0:
		print('No')
	elif c[0] % 2 == 0:
		print('No')
	else:
		print('Yes')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	max_count = 0
	same_count = 0
	for j in l:
		if j == 0:
			count = count + 1
		if j == 1:
			if count > max_count:
				same_count = max_count
				max_count = count
			elif count > same_count:
				same_count = count
			count = 0
	if max_count % 2 != 0 and same_count < (max_count + 1) / 2:
		print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	N = int(input())
	A = str(input()).split(' ')
	count = 0
	arrr = []
	flag = 0
	for a in A:
		if int(a) == 0:
			if not flag:
				flag = 1
				count = 1
			else:
				count = count + 1
		elif flag:
			flag = 0
			arrr.append(count)
	if flag:
		arrr.append(count)
	arrr.sort(reverse=True)
	if len(arrr) == 0 or arrr[0] % 2 == 0:
		print('No')
	elif len(arrr) == 1 or arrr[1] <= (arrr[0] - 1) // 2:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	lengths = [0]
	for i in range(n):
		if a[i] == 0:
			count += 1
		elif count != 0:
			lengths.append(count)
			count = 0
	large = max(lengths)
	lengths.remove(large)
	if large % 2 == 0:
		print('No')
	else:
		s_large = max(lengths)
		if s_large < (large + 1) / 2:
			print('Yes')
		else:
			print('No')


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

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

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	l = li()
	z = ans = 0
	for i in range(n):
		if l[i] == 0:
			z += 1
		else:
			ans = max(ans, z)
			z = 0
	ans = max(ans, z)
	if ans % 2 == 0:
		print('No')
	else:
		z = 0
		flag = Flag = 0
		for i in range(n):
			if l[i] == 0:
				z += 1
			else:
				if ans // 2 + 1 <= z:
					if flag:
						Flag = 1
						break
					else:
						flag = 1
				z = 0
		if Flag:
			print('No')
		else:
			print('Yes')


for _ in range(int(input())):
	n = int(input())
	s = input().split()
	l = sl = 0
	j = 0
	for k in range(n):
		i = s[k]
		if i == '0':
			j += 1
			continue
		else:
			if l < j:
				sl = l
				l = j
			elif l == j:
				sl = j
			elif j > sl:
				sl = j
			j = 0
	if l == 0:
		print('No')
	elif sl * 2 >= l:
		print('No')
	elif l % 2 == 0:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())

	def maxConsequtiveOnes(lst):
		_max = 0
		_ones = [0]
		for i in lst:
			if i == 0:
				_max += 1
			if i == 1:
				_max = 0
			_ones.append(_max)
		return max(_ones)
	a = list(map(int, input().split()))
	b = maxConsequtiveOnes(a)
	if b % 2 == 0:
		print('No')
	else:
		print('Yes')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	streaks = []
	curr_streak = 0
	for i in range(n):
		if l[i] == 0:
			curr_streak += 1
		else:
			if curr_streak > 0:
				streaks.append(curr_streak)
			curr_streak = 0
	num_ones = 0
	all_even_f = 1
	for e in streaks:
		if e == 1:
			num_ones += 1
		elif e % 2:
			all_even_f = 0
	if num_ones == 1 and set(streaks) == {1}:
		print('Yes')
		continue
	if all_even_f:
		print('No')
	else:
		print('Yes')


for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lar = seclar = 0
	prev = False
	cnt = 0
	for i in range(n):
		if prev is False:
			if lis[i] == 0:
				cnt = 1
				prev = True
			else:
				cnt = 0
				prev = False
		elif lis[i] == 0:
			cnt += 1
			prev = True
		else:
			if cnt > lar:
				seclar = lar
				lar = cnt
			elif cnt > seclar:
				seclar = cnt
			cnt = 0
			prev = False
	if lar == 0 and seclar == 30:
		print('No')
		continue
	if seclar == 0:
		if lar % 2 == 0:
			print('No')
		else:
			print('Yes')
		continue
	if lar % 2 == 0:
		print('No')
		continue
	if seclar > lar // 2:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	lio = [0]
	c = 0
	for i in range(n):
		if li[i] == 0:
			c = c + 1
		elif c != 0:
			lio.append(c)
			c = 0
	a = max(lio)
	lio.remove(a)
	if a % 2 == 0:
		print('No')
	else:
		b = max(lio)
		if (a + 1) // 2 > b:
			print('Yes')
		else:
			print('No')


import sys
sys.setrecursionlimit(10 ** 5)

def pro(arr):
	n = len(arr)
	lst = []
	i = 0
	while i < n:
		j = i
		if arr[i]:
			i += 1
			continue
		while j < n and arr[j] == 0:
			j += 1
		lst.append(j - 1 - i + 1)
		i = j + 1
	if lst == []:
		print('No')
		return
	if len(lst) == 1:
		if lst[0] % 2:
			print('Yes')
			return
		print('No')
		return
	lst.sort()
	(s, s2) = (lst[-1], lst[-2])
	c = lst.count(s)
	if s % 2 == 1 and s2 < (s + 1) // 2:
		print('Yes')
		return
	print('No')
n = int(input())
for i in range(n):
	n = int(input())
	arr = list(map(int, input().split()))
	pro(arr)


T = int(input())
for i in range(1, T + 1):
	a = int(input())
	s = input().split(' ')
	first = 1
	d = []
	e = ''
	q = 0
	for i in range(1, a - 1):
		if s[i] == '0':
			e += s[i]
		if s[i] == '0' and s[i + 1] == '1':
			d.append(e)
			e = ''
	d.sort()
	if len(d) > 0:
		last = d[-1]
		length = len(last)
		if len(d) > 1 and last == d[-2]:
			first = 1
		elif len(d) > 1 and len(d[-2]) >= length // 2 + 1:
			first = 1
		elif length % 2:
			first = 0
		elif not length % 2:
			first: first = 1
	else:
		first = 1
	print('Yes' if not first else 'No')


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	a = [0]
	c = 0
	m1 = m2 = 0
	for i in l:
		if i == 0:
			c += 1
		else:
			if c > m1:
				m2 = m1
				m1 = c
			elif c > m2:
				m2 = c
			c = 0
	o = m1
	e = m2
	if (o + 1) // 2 > e and o % 2 != 0:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	n = int(input())
	store = list(map(int, input().split()))
	count = 0
	curr = 0
	for i in range(n):
		if store[i] == 0:
			if curr > 0:
				curr += 1
			else:
				curr = 1
		else:
			if curr > count:
				count = curr
			curr = 0
	if curr > count:
		count = curr
	if count % 2 == 0:
		print('No')
	else:
		print('Yes')


from collections import Counter as C
R = lambda : input()
I = lambda : int(R())
M = lambda : map(int, R().split())
RS = lambda : map(str, R().split(' '))
L = lambda : list(M())
Nsum = lambda n: n * (n + 1) // 2

def Y():
	print('Yes')

def N():
	print('No')

def Countarr(li, n):
	i = 0
	mx = 0
	c = 0
	arr = []
	while i < n:
		if li[i]:
			mx = max(mx, c)
			arr.append(c)
			c = 0
		else:
			c += 1
		i += 1
	mx = max(mx, c)
	arr.append(c)
	return (C(arr), mx)
for _ in range(I()):
	n = I()
	li = L()
	(c, mx) = Countarr(li, n)
	f = True
	if c[mx] > 1:
		N()
	elif mx % 2 == 0:
		N()
	else:
		for j in range(1 + mx // 2, mx):
			if c[j]:
				N()
				f = False
				break
		if f:
			Y()


def isOdd(slen):
	m = -float('inf')
	mi = None
	for i in range(len(slen)):
		if slen[i] % 2 == 1 and slen[i] > m:
			mi = i
			m = slen[i]
	return mi

def find_even(slen, mi):
	for i in range(len(slen)):
		if i != mi and slen[i] > slen[mi] // 2:
			return False
	return True
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	slen = []
	i = 0
	while i < N:
		if A[i] == 0:
			e = i
			while e < N and A[e] == 0:
				e += 1
			slen.append(e - i)
			i = e + 1
		else:
			i += 1
	x = isOdd(slen)
	if len(slen) != 0 and x != None and find_even(slen, x):
		ans.append('Yes')
	else:
		ans.append('No')
for i in ans:
	print(i)


for iii in range(int(input())):
	n = int(input())
	s = input().split()
	s = ''.join(s).split('1')
	l = []
	for i in s:
		if len(i) == 0:
			continue
		else:
			l.append(i)
	l.sort(reverse=True, key=len)
	if len(l) == 0:
		print('No')
	elif len(l) == 1:
		if len(l[0]) % 2 == 0:
			print('No')
		else:
			print('Yes')
	else:
		(c, v) = (len(l[0]), len(l[1]))
		if c % 2 == 0:
			print('No')
		elif c % 2 and (c + 1) / 2 > v:
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(c, lis) = (0, [0])
	for i in a:
		if i == 0:
			c += 1
		else:
			if c > 0:
				lis.append(c)
			c = 0
	val = max(lis)
	if val % 2 == 0:
		print('No')
	else:
		lis.remove(val)
		val1 = max(lis)
		if (val + 1) // 2 > val1:
			print('Yes')
		else:
			print('No')


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	a = [0, 0, 0]
	while i != n:
		if l[i] == 0:
			count = 0
			while l[i] != 1:
				count += 1
				i += 1
				if i == n:
					break
			a.append(count)
		if i == n:
			break
		i += 1
	m = max(a)
	a.remove(m)
	s = max(a)
	if m % 2 != 0 and s < (m + 1) / 2:
		print('Yes')
	else:
		print('No')
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	z = 0
	ans = 0
	for i in range(n):
		if l[i] == 0:
			z += 1
		else:
			ans = max(ans, z)
			z = 0
	ans = max(ans, z)
	if ans % 2 == 0:
		print('No')
	else:
		z = 0
		flag = False
		ansFlag = False
		for i in range(n):
			if l[i] == 0:
				z += 1
			else:
				if ans // 2 + 1 <= z:
					if flag:
						ansFlag = True
						break
					else:
						flag = True
				z = 0
		if ansFlag:
			print('No')
		else:
			print('Yes')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	zs = []
	zeros = 0
	for i in a:
		if i == 1:
			zs.append(zeros)
			zeros = 0
		elif i == 0:
			zeros += 1
	zs.append(zeros)
	zs.sort()
	b = zs[-1]
	if b % 2 == 0:
		print('No')
	elif b % 2 == 1:
		if len(zs) == 1:
			print('Yes')
		else:
			nnum = b // 2 + 1
			tnum = max(b // 2, zs[-2])
			if nnum > tnum:
				print('Yes')
			else:
				print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	strip = list(input().split())
	dist = []
	k = 0
	for i in range(1, n):
		if strip[i] == '1':
			dist.append(i - k - 1)
			k = i
	dist.sort(reverse=True)
	if dist == []:
		print('No')
	elif len(dist) == 1:
		if dist[0] % 2 == 0:
			print('No')
		else:
			print('Yes')
	else:
		(m, m1) = (dist[0], dist[1])
		flag = 1 if (m + 1) // 2 > m1 and m % 2 != 0 else 0
		if flag:
			print('Yes')
		else:
			print('No')


t = int(input())
if 1 <= t <= 40000:
	for i in range(t):
		x = int(input())
		if 2 <= x <= 300000:
			y = input().split()
			z = ''
			for i in y:
				z += i
			z = z.split('1')
			z.sort()
			if len(z[len(z) - 1]) % 2 == 0:
				print('No')
			elif len(z[len(z) - 2]) > len(z[len(z) - 1]) / 2:
				print('No')
			else:
				print('Yes')


def find_two_max(bin):
	(max1, max2) = (0, 0)
	counter = 0
	for index in range(len(bin)):
		if bin[index] == '0':
			counter += 1
		else:
			if max1 < counter:
				max2 = max1
				max1 = counter
			elif max2 < counter:
				max2 = counter
			counter = 0
	if counter > 0:
		if max1 == max2:
			max1 = counter
		elif max1 < counter:
			max2 = max1
			max1 = counter
		elif max2 < counter:
			max2 = counter
	return (max1, max2)

def is_good(bin):
	(max1, max2) = find_two_max(bin)
	if max1 % 2 == 0:
		return False
	if max2 >= max1 // 2 + 1 and max2 != 0:
		return False
	return True

def handle_tests():
	num_of_tests = int(input())
	tests = []
	for i in range(num_of_tests):
		length = input()
		test = input()
		tests.append(test)
	for test in tests:
		bin = test.split()
		if is_good(bin):
			print('Yes')
		else:
			print('No')
handle_tests()