You are given a sequence $a_1, a_2, \ldots, a_n$. Each element of $a$ is $1$ or $2$.

Find out if an integer $k$ exists so that the following conditions are met.

$1 \leq k \leq n-1$, and

$a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$.

If there exist multiple $k$ that satisfy the given condition, print the smallest.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 1000$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2$).


-----Output-----

For each test case, if there is no such $k$, print $-1$.

Otherwise, print the smallest possible $k$.


-----Examples-----

Input
3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1
Output
2
-1
1


-----Note-----

For the first test case, $k=2$ satisfies the condition since $a_1 \cdot a_2 = a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 4$. $k=3$ also satisfies the given condition, but the smallest should be printed.

For the second test case, there is no $k$ that satisfies $a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n$

For the third test case, $k=1$, $2$, and $3$ satisfy the given condition, so the answer is $1$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Implementation

Complete search


Solutions:
def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(2) == 0:
		print(1)
		return
	elif a.count(2) % 2 == 1:
		print(-1)
		return
	else:
		cnt = a.count(2) // 2
		i = 0
		while cnt > 0:
			if a[i] == 2:
				cnt -= 1
			i += 1
		print(i)
	pass
for _ in range(int(input())):
	solve()


n = int(input())
for i in range(n):
	s = int(input())
	l = list(map(int, input().split()))
	d = l.count(2)
	if d % 2 == 1:
		print(-1)
	else:
		c = 0
		for i in range(s):
			if l[i] == 2:
				c += 1
			if c == d // 2:
				break
		print(i + 1)


for _ in range(int(input())):
	n = int(input())
	aa = list(map(int, input().split()))
	total = aa.count(2)
	if total % 2:
		print(-1)
		continue
	now = 0
	for i in range(n):
		if aa[i] == 2:
			now += 1
		if now == total // 2:
			print(i + 1)
			break


import sys
sys_input = sys.stdin.readline
sys_print = sys.stdout.write

def testcase():
	n = int(sys_input())
	arr = [*map(int, sys_input().split())]
	n_two = arr.count(2)
	if n_two % 2 == 1:
		print(-1)
		return
	cnt = 0
	for i in range(n):
		if arr[i] == 2:
			cnt += 1
		if cnt == n_two // 2:
			print(i + 1)
			return
t = int(sys_input())
for _ in range(t):
	testcase()


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count2 = 0
	for i in a:
		if i == 2:
			count2 += 1
	if count2 % 2 == 1:
		ans.append(-1)
	elif count2 == 0:
		ans.append(1)
	else:
		cou = 0
		for i in range(len(a)):
			if a[i] == 2:
				cou += 1
			if cou == count2 / 2:
				ans.append(i + 1)
				break
for i in ans:
	print(i)


n = int(input())
for i in range(n):
	m = int(input())
	v = list(map(int, input().split()))
	p = v.count(2)
	if p % 2 != 0:
		print('-1')
	else:
		q = 0
		for j in range(m):
			if v[j] == 2:
				q = q + 1
			if q == int(p / 2):
				print(j + 1)
				break


import collections
t = int(input())
for _ in range(t):
	n = int(input())
	seq = input().split(' ')
	cal = collections.Counter(seq)
	(cnt, rem) = divmod(cal['2'], 2)
	if rem:
		print(-1)
	elif cnt == 0:
		print(1)
	else:
		for i in range(n):
			if seq[i] == '2':
				cnt -= 1
				if cnt == 0:
					print(i + 1)
					break


def intRd():
	return int(input())

def lstRd():
	return list(map(int, input().split()))
for _ in range(intRd()):
	n = intRd()
	a = lstRd()
	cnt = a.count(2)
	if cnt & 1:
		print(-1)
	else:
		temp = 0
		for i in range(n):
			if a[i] == 2:
				temp += 1
			if temp == cnt // 2:
				print(i + 1)
				break


n = int(input())
for _ in range(n):
	k = int(input())
	L = list(map(int, input().split()))
	if max(L) == 1:
		print(1)
	elif L.count(2) % 2 == 1:
		print(-1)
	else:
		tc = L.count(2)
		twos = 0
		ind = 0
		for i in range(k):
			if L[i] == 2:
				twos += 1
			if twos == tc // 2:
				print(i + 1)
				break


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a.count(2)
	if x % 2 == 0 and x > 0:
		i = 0
		for y in range(0, n):
			if a[y] == 2:
				i += 1
			if i == x // 2:
				print(y + 1)
				break
	elif x == 0:
		print(1)
	else:
		print(-1)


n = int(input())
ans = []
for i in range(n):
	n1 = int(input())
	lis = list(map(int, input().split()))
	s = lis.count(2)
	if s == 0:
		ans.append(1)
		continue
	if s % 2 == 1:
		ans.append(-1)
	else:
		s1 = s // 2
		for j in range(n1):
			if lis[j] == 2:
				s1 -= 1
				if s1 == 0:
					ans.append(j + 1)
					break
for i in ans:
	print(i)


n_lines = int(input())

def count2s(list):
	c = 0
	for i in list:
		if i == '2':
			c += 1
	return c
for _ in range(n_lines):
	sequence_num = input()
	sequence = input().split(' ')
	num2 = count2s(sequence)
	if num2 == 0:
		print(1)
		continue
	if num2 % 2 != 0:
		print(-1)
		continue
	half2 = num2 / 2
	c = 0
	for i in range(len(sequence)):
		if sequence[i] == '2':
			c += 1
		if c == half2:
			break
	print(i + 1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	two = arr.count(2)
	if two == 0:
		print(1)
	elif two % 2 == 1:
		print(-1)
	else:
		res = -1
		a = 0
		for i in range(n):
			if arr[i] == 2:
				a += 1
			if a == two // 2:
				res = i + 1
				break
		print(res)


def f():
	n = int(input())
	array = list(map(int, input().split()))
	number = array.count(2)
	if number % 2 != 0:
		print('-1')
		return
	elif number == 0:
		print(1)
	else:
		counter = 0
		for (ind, x) in enumerate(array):
			if x == 2:
				counter += 1
				if counter == number // 2:
					print(ind + 1)
					return
batch = int(input())
for _ in range(batch):
	f()


def mina(n, arr):
	twos = arr.count(2)
	if twos % 2 == 1:
		return -1
	elif twos == 0:
		return 1
	else:
		rep = 0
		for k in range(0, n):
			if arr[k] == 2:
				rep += 1
				if rep == int(twos / 2):
					return k + 1
t = int(input())
for _ in range(0, t):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	response = mina(n, arr)
	print(f'{response}')


t = int(input())
k = []
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(2) % 2 == 1:
		k.append(-1)
	elif l.count(2) % 2 == 0:
		n = l.count(2) / 2
		count = 0
		for i in range(len(l)):
			if l[i] == 2:
				count += 1
			if count == n:
				break
		k.append(i + 1)
	elif l.count(2) == 0:
		k.append(1)
for i in k:
	print(i)


for i in range(int(input())):
	int(input())
	a = list(map(int, input().split()))
	j = a.count(2)
	k = 0
	if j % 2 == 1:
		print('-1')
	else:
		for z in range(len(a)):
			if a[z] == 2:
				k += 1
			if k == j // 2:
				print(z + 1)
				break


t = int(input())
for c in range(0, t):
	v = int(input())
	n = list(map(int, input().split()))
	x = n.count(2)
	j = x // 2
	y = 2 ** (x - 1)
	if x % 2 == 1:
		print(-1)
	elif x == 0:
		print(1)
	else:
		l = [i for (i, b) in enumerate(n) if b == 2][j - 1]
		print(l + 1)


t = int(input())
for times in range(t):
	n = int(input())
	inp = input()
	arr = inp.split()
	twos = 0
	for a in arr:
		if a == '2':
			twos += 1
	if twos % 2:
		print(-1)
		continue
	two = 0
	for i in range(n):
		if arr[i] == '2':
			two += 1
		if two == twos // 2:
			print(i + 1)
			break


for s in [*open(0)][2::2]:
	k = i = s.count('2')
	j = 0
	while (i := (i - 2 * (s[j] > '1'))) > 0:
		j += 2
	print((j // 2 + 1, -1)[k % 2])


def one_and_two(liste):
	number_two = liste.count(2)
	if number_two % 2 == 1:
		return -1
	else:
		count = 0
		for i in range(len(liste)):
			if liste[i] == 2:
				count += 1
			if count == number_two / 2:
				return i + 1
tests = int(input())
for i in range(tests):
	length = int(input())
	liste = list(map(int, input().split(' ')))
	print(one_and_two(liste))


for i in range(int(input())):
	n = input()
	a = input().split()
	c = a.count('2')
	if c == 0:
		print('1')
	elif c % 2:
		print('-1')
	else:
		c /= 2
		k = 0
		while c:
			k = a.index('2', k)
			c -= 1
			k += 1
		print(k)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(2)
	t = 0
	r = 1
	if c & 1:
		print(-1)
		continue
	for i in range(n):
		if a[i] == 2:
			t += 1
		if t == c // 2:
			r = i + 1
			break
	print(r)


n = int(input())
for i in range(n):
	l = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	amt = a.count(2)
	if amt % 2 != 0:
		print(-1)
		continue
	for j in range(l):
		if a[j] == 2:
			cnt += 1
		if cnt == amt // 2:
			print(j + 1)
			break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ones = arr.count(1)
	if ones == n:
		print(1)
	else:
		two = arr.count(2)
		if two & 1:
			print(-1)
		else:
			req = two // 2
			index = -1
			for i in range(n):
				if arr[i] == 2:
					req -= 1
					if req == 0:
						index = i + 1
						break
			if 1 <= index <= n - 1:
				print(index)
			else:
				print(-1)


size = int(input())
for _ in range(size):
	n = int(input())
	arr = list(map(int, input().split()))
	count = arr.count(2)
	if count == 0:
		print(1)
	elif count % 2 == 1:
		print(-1)
	else:
		val = count / 2
		c = 0
		i = 0
		while c != val:
			if arr[i] == 2:
				c += 1
			i += 1
		print(i)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(2)
	if c == 0:
		print(1)
	elif c % 2:
		print(-1)
	else:
		k = 0
		for i in range(n):
			if a[i] == 2:
				k += 1
			if k == c // 2:
				print(i + 1)
				break


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = l.count(2)
	if x % 2 != 0:
		print(-1)
	else:
		l1 = [i for i in range(n) if l[i] == 2]
		if len(l1) > 0:
			y = l1[len(l1) // 2 - 1] + 1
			print(y)
		else:
			print(1)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	if l.count(2) % 2:
		print(-1)
	elif l.count(2) == 0:
		print(1)
	elif l.count(2) % 2 == 0:
		a = l.count(2) // 2
		k = 0
		for j in range(n):
			if l[j] == 2:
				k += 1
			if k == a:
				print(j + 1)
				break


m = int(input())
for _ in range(m):
	n = int(input())
	l = list(map(int, input().split()))
	p = l.count(2)
	if p % 2 != 0:
		print(-1)
	elif p == 0:
		print(1)
	else:
		c = 0
		for j in range(n):
			if l[j] == 2:
				c += 1
			if c == p // 2:
				break
		print(j + 1)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(2) == 0:
		print(1)
	elif arr.count(2) % 2 == 1:
		print(-1)
	else:
		count_2 = arr.count(2)
		two = 0
		for i in range(n):
			if arr[i] == 2:
				two += 1
			if two == count_2 / 2:
				print(i + 1)
				break


def solve():
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	two = 0
	for i in range(n):
		if a[i] == 2:
			two += 1
	if two % 2 == 1:
		print(-1)
	else:
		current_two = 0
		k = -1
		for i in range(n):
			if a[i] == 2:
				current_two += 1
			if current_two == two // 2:
				k = i
				break
		print(k + 1)
t = int(input().strip())
for _ in range(t):
	solve()


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	(one, two) = (0, 0)
	for i in range(n):
		if a[i] == 1:
			one += 1
		else:
			two += 1
	if not two:
		print(1)
		return
	if two % 2:
		print(-1)
		return
	cnt = 0
	for i in range(n - 1):
		if a[i] == 2:
			cnt += 1
		if cnt == two // 2:
			print(i + 1)
			return
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	cnt = lst.count(2)
	ct = 0
	ct1 = 0
	if cnt == 0:
		print(1)
	elif cnt % 2 == 0:
		for i in lst:
			ct1 += 1
			if i == 2:
				ct += 1
				if ct == cnt // 2:
					print(ct1)
					break
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.count(2)
	b = l.count(1)
	c = 0
	if a % 2 != 0:
		print(-1)
	elif a == 0:
		print(1)
	else:
		for i in range(n):
			if l[i] == 2:
				c = c + 1
				if c == a // 2:
					print(i + 1)
					break


import sys, os
TC = True

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	c2 = 0
	for i in range(n):
		if arr[i] == 2:
			c2 += 1
	if c2 % 2:
		print(-1)
		return
	else:
		current = 0
		k = -1
		for i in range(n):
			if arr[i] == 2:
				current += 1
			if current == c2 // 2:
				k = i
				break
		print(k + 1)
if os.path.exists('input.txt'):
	debug = True
	sys.stdin = open('input.txt', 'r')
if TC:
	for _ in range(int(input())):
		solve()
else:
	solve()


try:
	for i in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		c = l.count(2)
		if l.count(2) % 2 != 0:
			print(-1)
		elif c == 0:
			print(1)
		else:
			temp = 0
			index = -1
			for i in range(len(l)):
				if l[i] == 2:
					temp += 1
				if temp == c // 2:
					index = i
					break
			print(index + 1)
except:
	pass


for q in range(int(input())):
	n = int(input())
	s = input().split(' ')
	c = 0
	for i in s:
		if i == '2':
			c += 1
	if c == 0:
		print(1)
	elif c % 2 != 0:
		print(-1)
	else:
		j = 0
		k = 0
		for x in s:
			j += 1
			if x == '2':
				k += 1
				if k == c / 2:
					break
		print(j)


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	l = list(map(int, input().split()))
	m = l.count(2)
	for j in range(0, len(l) - 1):
		if l[j] == 2:
			c += 1
		if c == m // 2:
			break
	if m == 0:
		print(1)
	elif m % 2 != 0:
		print(-1)
	else:
		print(j + 1)


t = int(input())
for i in range(t):
	n = int(input())
	an = list(map(int, input().split()))
	answer = 0
	twos = an.count(2)
	pivot = int(twos / 2)
	count = 0
	if twos == 0:
		answer = 1
	elif twos % 2 == 0:
		for k in range(n - 1):
			if an[k] == 2:
				count += 1
				if count == pivot:
					answer = k + 1
	else:
		answer = -1
	print(answer)


for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	c = lst.count(2)
	if c % 2 == 1:
		print(-1)
	else:
		c //= 2
		for i in range(n):
			if lst[i] == 2:
				c -= 1
			if c == 0:
				print(i + 1)
				break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	k = arr.count(2)
	if k % 2 != 0:
		print(-1)
	elif k == 0:
		print(1)
	elif k % 2 == 0:
		x = k / 2
		c = 0
		for i in range(len(arr)):
			if arr[i] == 2:
				c += 1
			if c == x:
				break
		print(i + 1)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	counter = 0
	k = a.count(2)
	if k % 2 == 1:
		print(-1)
	elif k == 0:
		print(1)
	else:
		for i in range(len(a)):
			if a[i] == 2:
				counter += 1
			if counter == k // 2:
				print(i + 1)
				break


def stage_two(n, v, horisan):
	madara = 0
	for i in range(n - 1):
		if v[i] == 2:
			madara += 1
		if madara == horisan / 2:
			return i + 1

def solve_problem(n, v):
	(miyamura, horisan) = (0, 0)
	for i in range(n):
		if v[i] == 1:
			miyamura += 1
		else:
			horisan += 1
	if horisan == 0:
		return 1
	if horisan % 2:
		return -1
	return stage_two(n, v, horisan)
testcase = int(input().strip())
for i in range(testcase):
	n = int(input().strip())
	v = list(map(int, input().strip().split()))
	print(solve_problem(n, v))


for t in range(int(input())):
	n = int(input())
	(a, b) = ([int(_) for _ in input().split()], [])
	c = a.count(2)
	if c == 0 and a.count(1) > 1:
		print(1)
	elif c % 2:
		print(-1)
	elif c == 2:
		print(a.index(2) + 1)
	else:
		c = int(c / 2)
		i = 0
		while c:
			if a[i] == 2:
				c -= 1
			i += 1
		print(i)


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	arr = list(map(int, input().split()))
	count = 0
	twos = arr.count(2)
	if twos == 0:
		count = 1
	elif twos % 2 == 0:
		da_numba = twos / 2
		for j in range(len(arr)):
			if arr[j] == 2:
				count += 1
			if count == da_numba:
				count = j + 1
				break
	else:
		count = -1
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(2) % 2 == 1:
		print(-1)
	else:
		k = arr.count(2) // 2
		(ans, cnt) = (0, 0)
		for i in range(n):
			if arr[i] == 2:
				cnt += 1
			if cnt == k:
				print(i + 1)
				break


test_cases = int(input())
for i in range(test_cases):
	num = int(input())
	num_list = list(input().split())
	count = num_list.count('2')
	if count % 2 == 1:
		print('-1')
	elif count == 0:
		print('1')
	else:
		j = 0
		pos = -1
		while j < count / 2:
			pos = num_list.index('2', pos + 1, len(num_list))
			j += 1
		print(pos + 1)


t = int(input())
for i in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	c = array.count(2)
	if c == 0:
		print(1)
	elif c % 2 == 0:
		b = 0
		a = 1
		for j in array:
			if j == 2:
				b += 1
				if b == c / 2:
					print(a)
			a += 1
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.count(2)
	if b % 2 == 1:
		print(-1)
	else:
		count = 0
		i = 0
		while count < b // 2:
			if a[i] == 2:
				count += 1
			i += 1
		if i == 0:
			i += 1
		print(i)


q = int(input())
for test in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if a[i] == 2:
			count += 1
	if count % 2 == 1:
		print(-1)
		continue
	count_l = 0
	for i in range(n):
		if a[i] == 2:
			count_l += 1
		if count_l == count // 2:
			print(i + 1)
			break


t = int(input())
for tc in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	two = lst.count(2)
	(cnt, k, f) = (0, 0, 0)
	while k < n:
		if lst[k] == 2:
			cnt += 1
		k += 1
		if two - cnt == cnt:
			f = 1
			break
	if f == 1:
		print(k)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = arr.count(2)
	if cnt & 1:
		print(-1)
		continue
	cnt >>= 1
	for i in range(n - 1):
		if arr[i] == 2:
			cnt -= 1
		if cnt == 0:
			print(i + 1)
			break


def check(b):
	if b.count(2) % 2:
		return -1
	else:
		c = [i for i in range(len(b)) if b[i] == 2]
		if len(c) == 0:
			return 1
		else:
			return c[len(c) // 2 - 1] + 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(a))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c1 = Counter(l)
	if c1[2] % 2 != 0:
		print(-1)
	elif c1[2] == 0:
		print(1)
	else:
		req = c1[2] // 2
		for j in range(n):
			if req != 0:
				if l[j] == 2:
					req -= 1
			else:
				print(j)
				break


def f(nums):
	two_indexes = [i for (i, num) in enumerate(nums) if num == 2]
	if len(two_indexes) % 2:
		print(-1)
	elif len(two_indexes) == 0:
		print(1)
	else:
		print(two_indexes[(len(two_indexes) - 1) // 2] + 1)
n = int(input())
for _ in range(n):
	_ = input()
	nums = list(map(int, input().split()))
	f(nums)


import sys
import socket
hostnames = ['N551J', 'FVFH32CDQ05N', 'X553M']
input_file = 'a1.in'
if socket.gethostname() in hostnames:
	sys.stdin = open(input_file)

def read_int_list():
	return list(map(int, input().split()))

def read_int():
	return int(input())

def read_str_list():
	return input().split()

def read_str():
	return input()

def solve():
	t = read_int()
	res = [-1] * t
	for i in range(t):
		n = read_int()
		a = read_int_list()
		m = a.count(2)
		if m % 2 == 0:
			ind = 0
			for j in range(n):
				if a[j] == 2:
					ind += 1
				if ind == m // 2:
					res[i] = j + 1
					break
	return res

def main():
	res = solve()
	print(*res, sep='\n')
main()


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	k = 0
	for i in l:
		if i == 2:
			c += 1
	if c == 0:
		print(1)
	elif c % 2 == 1:
		print(-1)
	else:
		for i in range(n):
			if l[i] == 2:
				k += 1
				if k == c // 2:
					print(i + 1)
					break


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	two = a.count(2)
	if two & 1:
		print(-1)
	elif two == 0:
		print(1)
	else:
		c = 0
		for (j, i) in enumerate(a):
			if i == 2:
				c += 1
			if c == two // 2:
				print(j + 1)
				break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = 0
	inil2 = 0
	inir2 = arr.count(2)
	if inir2 == 0:
		print(1)
	else:
		for i in range(1, n):
			if arr[i - 1] == 2:
				inil2 += 1
				inir2 -= 1
				if inil2 == inir2:
					print(i)
					flag = 1
					break
				else:
					flag = 0
		if flag == 0:
			print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	Z = list(map(int, input().split()))
	K = []
	s = sum(Z) - n
	if s % 2 == 1:
		print(-1)
		continue
	c = 0
	for j in range(n):
		if Z[j] == 2:
			c += 1
		if c == s // 2:
			print(j + 1)
			break


def solve():
	t = 1
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		a = [int(x) for x in input().split()]
		a_count = a.count(2)
		if a_count % 2 != 0:
			print(-1)
		else:
			half_2 = a_count / 2
			for i in range(n):
				if a[i] == 2:
					half_2 -= 1
				if not half_2:
					print(i + 1)
					break
solve()


def solve():
	n = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	two = a.count(2)
	if two & 1:
		print(-1)
	else:
		current_twoool = 0
		k = -1
		for i in range(n):
			if a[i] == 2:
				current_twoool += 1
			if current_twoool == two // 2:
				k = i
				break
		print(k + 1)
t = int(input().strip())
for _ in range(t):
	solve()


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	a = [int(k) for k in inps()]
	l = []
	s = 0
	for i in a:
		if i == 2:
			s = s + 1
		l.append(s)
	k = l[-1]
	for (j, i) in enumerate(l):
		if k - i == i:
			print(j + 1)
			return
	print(-1)

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


n = int(input())
for i in range(n):
	x = int(input())
	a = list(map(int, input().split()))
	twos = 0
	for i in a:
		if i == 2:
			twos += 1
	if twos % 2 == 0 and twos != 0:
		two = 0
		for i in range(len(a)):
			if a[i] == 2:
				two += 1
			if two == twos // 2:
				print(i + 1)
				break
	elif twos % 2 == 1:
		print(-1)
	else:
		print(1)


total = int(input())

def func():
	size = int(input())
	l = [int(c) for c in input().split()]
	count_2 = l.count(2)
	if count_2 % 2 == 1:
		print(-1)
		return
	half = count_2 // 2
	for (i, val) in enumerate(l):
		if val == 2:
			half -= 1
		if not half:
			print(i + 1)
			break
for _ in range(total):
	func()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = a.count(2)
	if cnt == 0:
		print(1)
		continue
	if cnt % 2 == 0:
		ans = [i for (i, x) in enumerate(a) if x == 2][cnt // 2 - 1]
		print(ans + 1)
	else:
		print(-1)


for _ in range(int(input())):
	www = int(input())
	arrrr = list(map(int, input().split()))
	x = 0
	y = 0
	for i in range(www):
		if arrrr[i] == 1:
			x = x + 1
		else:
			y = y + 1
	if y == 0:
		print(1)
		continue
	if y % 2:
		print(-1)
		continue
	oops = 0
	for i in range(www - 1):
		if arrrr[i] == 2:
			oops = oops + 1
		if oops == y / 2:
			print(i + 1)
			break


import collections

def one_and_two(n, nums):
	cnt = collections.Counter(nums)
	if cnt[2] % 2 != 0:
		return -1
	if cnt[2] == 0:
		return 1
	k = 0
	target = cnt[2] >> 1
	for i in range(n):
		if nums[i] & 1:
			continue
		k += 1
		if k == target:
			return i + 1
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(one_and_two(n, l))


from math import prod
T = int(input())
for t in range(T):
	N = int(input())
	nums = [int(x) for x in input().split()]
	n2 = nums.count(2)
	if n2 % 2:
		print(-1)
	else:
		n2s = 0
		for (i, n) in enumerate(nums):
			if n == 2:
				n2s += 1
			if n2s == n2 // 2:
				print(i + 1)
				break


h = int(input())
for fgh in range(h):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.count(2)
	if b % 2 == 1:
		print(-1)
	else:
		m = 0
		for i in range(n):
			if a[i] == 2:
				m += 1
				b -= 1
			if b == m:
				print(i + 1)
				break


import math as m
for i1 in range(int(input())):
	i1 = int(input())
	a1 = list(map(int, input().split()))
	a = a1.count(2)
	if a == 0:
		print(1)
	elif not a % 2 == 0:
		print(-1)
	else:
		a2 = []
		for i2 in range(len(a1)):
			if a1[i2] == 2:
				a2.append(i2)
		print(a2[a // 2 - 1] + 1)


t = int(input())
for i in range(t):
	a = int(input())
	l = list(map(int, input().split()))
	c = 0
	c1 = 0
	for i in l:
		if i == 4 // 2:
			c1 = c1 + 1
	if c1 == 2 - 2:
		print(1)
	elif c1 % 2 == 1:
		print(-1)
	else:
		b = c1 // 2
		for i in range(a):
			if l[i] == 2:
				c = c + 1
			if c == b:
				print(i + 2 // 2)
				break


def fun(a, t):
	cnt = t.count(2)
	if cnt == 0:
		return 1
	if cnt % 2 == 1:
		return -1
	k = -1
	count = 0
	for i in range(a):
		if t[i] == 2:
			count += 1
			if count == cnt / 2:
				k = i + 1
	return k
for _ in range(int(input())):
	a = int(input())
	t = [int(i) for i in input().split()]
	print(fun(a, t))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a.count(2)
	k = 0
	if s == 0:
		print(1)
	elif s % 2 != 0:
		print(0 - 1)
	elif s % 2 == 0:
		m = s // 2
		for i in a:
			k += 1
			if i == 2:
				m -= 1
			if m == 0:
				break
		print(k)


def product(arr, N):
	count_2r = 0
	for i in range(N):
		if arr[i] == 2:
			count_2r += 1
	count_2l = 0
	for j in range(1, N):
		if arr[j - 1] == 2:
			count_2l += 1
			count_2r -= 1
		if count_2l == count_2r:
			return j
	return -1
t = int(input())
while t:
	N = int(input())
	arr = [int(i) for i in input().split(' ')]
	k = product(arr, N)
	print(k)
	t -= 1


import sys
sys.setrecursionlimit(10 ** 9)

def ans(L):
	c = L.count(2)
	if c % 2 == 1:
		return -1
	if c == 0:
		return 1
	j = 1
	nc = 0
	while True:
		if L[j - 1] == 2:
			nc += 1
			if nc == c // 2:
				return j
		j += 1
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(ans(l))


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().rstrip().split()]
	co = a.count(2)
	if co % 2 != 0:
		print(-1)
	elif 2 not in a:
		print(1)
	else:
		co = a.count(2)
		ans = -1
		b = 0
		for i in range(0, n):
			if a[i] == 2:
				b += 1
				if b == co // 2:
					ans = i + 1
					break
		print(ans)


def func(li, n):
	count1 = 0
	count2 = 0
	count = 0
	for i in li:
		if i == 1:
			count1 += 1
		else:
			count2 += 1
	if count2 == 0:
		return 1
	if count2 % 2 != 0:
		return -1
	else:
		for i in range(len(li)):
			if li[i] == 2:
				count += 1
				if count == count2 // 2:
					return i + 1
t = int(input())
for i in range(t):
	n = int(input())
	li = [int(item) for item in input().split()]
	print(func(li, n))


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	if len(set(nums)) == 1:
		if nums[0] == 1:
			print(1)
			continue
	x = nums.count(2)
	if x % 2 != 0:
		print(-1)
		continue
	else:
		ans = 0
		two = 0
		for i in nums:
			if two == x // 2:
				print(ans)
				break
			ans += 1
			if i == 2:
				two += 1


t = int(input())
for i in range(t):
	n = int(input())
	c = [int(m) for m in input().split()]
	if n == sum(c):
		print(1)
	elif (sum(c) - n) % 2 == 0:
		k = [i for i in range(n) if c[i] == 2]
		print(k[len(k) // 2 - 1] + 1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(2)
	e = c // 2
	d = f = 0
	for i in range(n):
		if a[i] == 2:
			d += 1
		if e == d:
			f = i + 1
			break
	if c % 2 == 0:
		print(f)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	if max(A) == 1:
		print(1)
	else:
		cnt = A.count(2)
		if cnt % 2:
			print(-1)
		else:
			cnt //= 2
			for i in range(n):
				cnt -= 1 if A[i] == 2 else 0
				if cnt == 0:
					print(i + 1)
					break


n = int(input())
for _ in range(n):
	t = 0
	n1 = int(input())
	a = list(map(int, input().split()))
	c = a.count(2)
	if c & 1:
		print('-1')
	else:
		for i in range(n1):
			if a[i] == 2:
				t += 1
			if t == c // 2:
				print(i + 1)
				break


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	two = 0
	for x in a:
		if x == 2:
			two += 1
	if two % 2:
		print(-1)
	else:
		count = 0
		for i in range(n):
			if a[i] == 2:
				count += 1
			if count == two // 2:
				print(i + 1)
				break


n = int(input())
for i in range(n):
	length = int(input())
	count = 0
	lis = [int(j) for j in input().split()]
	count = lis.count(2)
	if count % 2:
		print(-1)
	elif count == 0:
		print(1)
	else:
		c = 0
		for j in range(len(lis)):
			if c == count // 2:
				print(j)
				break
			if lis[j] == 2:
				c += 1


l = []
t = int(input())
for _ in range(t):
	n = int(input())
	sp = list(map(int, input().split()))[:n]
	if sp.count(2) % 2 == 1:
		print(-1)
	else:
		for i in range(n):
			if sp[i] == 2:
				l.append(i + 1)
		if len(l) == 0:
			print(1)
		else:
			print(l[len(l) // 2 - 1])
		l.clear()


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	n2 = A.count(2)
	if n2 % 2 != 0:
		print(-1)
	elif n2 == 0:
		print(1)
	else:
		s = 0
		for i in range(n):
			if A[i] == 2:
				s += 1
				if s == n2 // 2:
					print(i + 1)
					break
		else:
			print(-1)