You are given an array A of length N containing the elements -1 and 1 only. Determine if it is possible to rearrange the array A in such a way that A_{i} is not the geometric mean of A_{i-1} and A_{i+1}, for all i such that 2 ≤ i ≤ N-1.

Y is said to be the geometric mean of X and Z if Y^{2} = X \cdot Z.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output Yes if it is possible to rearrange A in such a way that A_{i} is not the geometric mean of A_{i-1} and A_{i+1}, where 2 ≤ i ≤ N-1. Otherwise output No.

You may print each character of Yes and No in uppercase or lowercase (for example, yes, yEs, YES will be considered identical).

------ Constraints ------ 

$1 ≤ T ≤ 200$
$3 ≤ N ≤ 1000$
$A_{i} \in \{ -1, 1 \}$

----- Sample Input 1 ------ 
3
5
1 1 1 -1 -1
3
1 1 1
6
1 -1 -1 -1 -1 1

----- Sample Output 1 ------ 
Yes
No
Yes

----- explanation 1 ------ 
Test case 1: We can rearrange the array $A$ to $[1, 1, -1, -1, 1]$. One can see that ${A_{i}}^2 \neq A_{i-1} \cdot A_{i+1}$, for any $2 ≤ i ≤ N-1$.

Test case 2: None of the rearrangements of $A$ satisy the given condition.

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minuscount = a.count(-1)
	pluscount = a.count(1)
	if n % 2 == 0:
		if n / 2 % 2 != 0:
			print('Yes' if max(minuscount, pluscount) - min(minuscount, pluscount) <= 2 else 'No')
		elif n / 2 % 2 == 0:
			print('Yes' if max(minuscount, pluscount) - min(minuscount, pluscount) == 0 else 'No')
	elif n % 2 != 0:
		print('Yes' if max(minuscount, pluscount) - min(minuscount, pluscount) <= 1 else 'No')
	else:
		print('NO')


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(1)
	b = l.count(-1)
	if abs(a - b) < 2:
		print('Yes')
	elif abs(a - b) == 2:
		if a % 2 == 0 and b % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(pos, neg) = (0, 0)
	for ele in arr:
		if ele == 1:
			pos += 1
		else:
			neg += 1
	if abs(pos - neg) < 2:
		print('Yes')
	elif abs(pos - neg) == 2:
		if pos % 2 == 0 and neg % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	if N % 4 == 0:
		if A.count(1) == A.count(-1):
			print('Yes')
		else:
			print('No')
	elif N % 4 == 1 or N % 4 == 3:
		if abs(A.count(1) - A.count(-1)) == 1:
			print('Yes')
		else:
			print('No')
	elif abs(A.count(1) - A.count(-1)) == 0 or abs(A.count(1) - A.count(-1)) == 2:
		print('Yes')
	else:
		print('No')


t = int(input())
for tc in range(t):
	x = int(input())
	l = list(map(int, input().split()))
	p = l.count(1)
	n = l.count(-1)
	if abs(p - n) < 2:
		print('Yes')
	elif abs(p - n) == 2:
		if p % 2 == 0 and n % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c1 = a.count(1)
	c2 = a.count(-1)
	if abs(c1 - c2) < 2:
		print('Yes')
	elif abs(c1 - c2) == 2:
		if c2 % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(-1)
	b = l.count(1)
	if abs(a - b) < 2:
		print('Yes')
	elif abs(a - b) == 2:
		if b & 1:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


num = set((0, 2, 4))
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = arr.count(1)
	b = arr.count(-1)
	if abs(a - b) < 2:
		print('Yes')
	elif abs(a - b) == 2:
		if b & 1:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s1 = a.count(-1)
	s2 = a.count(1)
	if len(set(a)) == 1:
		print('No')
	elif abs(s1 - s2) < 2:
		print('Yes')
	elif abs(s1 - s2) == 2:
		if s1 & 1:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	(x, y) = (0, 0)
	for j in l:
		if j == -1:
			x += 1
		else:
			y += 1
	if abs(x - y) < 2:
		print('Yes')
	elif abs(x - y) == 2:
		if x % 2 == 1:
			print('No')
		else:
			print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if abs(a.count(-1) - a.count(1)) < 2:
		print('Yes')
	elif abs(sum(a)) == 2:
		if a.count(-1) % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = l.count(-1)
	if abs(sum(l)) < 2:
		print('Yes')
	elif abs(sum(l)) == 2:
		if x % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos = a.count(1)
	neg = a.count(-1)
	dif = abs(pos - neg)
	if dif == 0:
		ans = 'Yes'
	elif dif == 1 and n % 2 == 1:
		ans = 'Yes'
	elif dif == 2 and n % 4 == 2:
		ans = 'Yes'
	else:
		ans = 'No'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minuses = a.count(-1)
	delta = abs(2 * minuses - n)
	rem = n % 4
	if rem == 0 and delta == 0:
		print('Yes')
	elif rem == 2 and delta in [0, 2]:
		print('Yes')
	elif delta == 1:
		print('Yes')
	else:
		print('No')


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	r = abs(a.count('1') - a.count('-1'))
	if n % 4 == 0:
		if r == 0:
			print('Yes')
			continue
	elif n % 4 == 2:
		if r == 0 or r == 2:
			print('Yes')
			continue
	elif r == 1:
		print('Yes')
		continue
	print('No')


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	x = A.count(-1)
	y = A.count(1)
	if abs(sum(A)) < 2:
		print('Yes')
	elif abs(sum(A)) == 2:
		if x % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


def solve(n, lst):
	pos = lst.count(1)
	neg = lst.count(-1)
	if abs(pos - neg) < 2 or (abs(pos - neg) == 2 and pos & 1 == 0 and (neg & 1 == 0)):
		print('Yes')
	else:
		print('No')
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	solve(n, lst)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	negative = 0
	positive = 0
	for x in arr:
		if x < 0:
			negative += 1
		else:
			positive += 1
	diff = abs(positive - negative)
	if positive & 1 or negative & 1:
		if diff <= 1:
			print('Yes')
		else:
			print('No')
	elif diff <= 2:
		print('Yes')
	else:
		print('No')


import math
for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	if n % 2 != 0:
		a1 = math.floor(n / 2)
		a2 = n - a1
		if a.count(-1) == a1 and a.count(1) == a2 or (a.count(-1) == a2 and a.count(1) == a1):
			print('Yes')
		else:
			print('No')
	elif n % 4 == 0:
		if a.count(-1) == a.count(1):
			print('Yes')
		else:
			print('No')
	else:
		a1 = math.floor(n / 2) + 1
		a2 = math.floor(n / 2) - 1
		if a.count(-1) == a1 and a.count(1) == a2 or (a.count(-1) == a2 and a.count(1) == a1):
			print('Yes')
		elif a.count(-1) == a.count(1):
			print('Yes')
		else:
			print('No')


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	cnt_a = 0
	cnt_b = 0
	for i in range(n):
		if a[i] == 1:
			cnt_a += 1
		else:
			cnt_b += 1
	mn = min(cnt_a, cnt_b)
	mx = max(cnt_a, cnt_b)
	if mx <= 2 and mn == 1:
		print('Yes')
	elif mx > 2 and mn == 1:
		print('No')
	elif mn == 0:
		print('No')
	elif n % 2 == 0 and mx % 2 == 0 and (mx - mn <= 2):
		print('Yes')
	elif n % 2 == 0 and mx % 2 != 0 and (mx == mn):
		print('Yes')
	elif n % 2 == 0 and mx % 2 != 0 and (mx != mn):
		print('No')
	elif n % 2 != 0 and mx - mn <= 1:
		print('Yes')
	else:
		print('No')


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	diff = abs(sum(arr))
	if diff > 2:
		print('No')
	elif n % 4 == 0 and diff > 0:
		print('No')
	else:
		print('Yes')


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	(a, b) = (m.count(-1), m.count(1))
	t = abs(a - b)
	if t < 2:
		print('Yes')
	elif t == 2 and a % 2 == 0 and (b % 2 == 0):
		print('Yes')
	else:
		print('No')


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	s = abs(s)
	if s > 2:
		print('No')
		continue
	elif n % 4 == 0 and s > 0:
		print('No')
		continue
	print('Yes')


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = A.count(-1)
	C = A.count(1)
	flag = True
	(a, b) = (min(C, B), max(C, B))
	if N % 2 == 1:
		if b - a == 1:
			print('Yes')
		else:
			print('No')
	elif N % 4 == 0:
		if a == b:
			print('Yes')
		else:
			print('No')
	elif a == b or b - a == 2:
		print('Yes')
	else:
		print('No')


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	p = A.count(1)
	n = A.count(-1)
	if abs(p - n) < 2:
		print('Yes')
	elif abs(p - n) == 2:
		if p % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


for i in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	neg = l.count(-1)
	pos = l.count(1)
	if abs(neg - pos) < 2:
		print('Yes')
	elif abs(neg - pos) == 2:
		if neg % 2 == 0:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


T = int(input())
for each_case in range(T):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	if n % 2 == 0:
		if abs(arr.count(-1) - arr.count(1)) == 0 and n % 4 == 0:
			print('Yes')
		elif abs(arr.count(-1) - arr.count(1)) in (0, 2) and n % 4 == 2:
			print('Yes')
		else:
			print('No')
	elif abs(arr.count(-1) - arr.count(1)) == 1:
		print('Yes')
	else:
		print('No')