Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has invested his savings into $N$ coins (numbered $1$ through $N$). For each valid $i$, the $i$-th coin has value $A_{i}$. Chef does not want to know how much money he has, so he remembers the mean value of the coins instead of the sum of their values.

A waiter from Chef's restaurant plans to steal exactly one of Chef's coins, but he does not want Chef to know about this, so he can only steal a coin if the arithmetic mean of all remaining coins is the same as the original arithmetic mean of all coins. Since the waiter is not good at mathematics, can you help him complete his plan?

You have to determine whether it is possible to steal some coin and if it is possible, choose the coin the waiter should steal. If there are multiple coins that can be stolen, choose the one with the smallest number.

------  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. If the waiter cannot steal any coin, this line should contain the string "Impossible" (without quotes). Otherwise, it should contain the number of the coin he should steal.

------  Constraints ------
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points):
$2 ≤ N ≤ 10^{3}$
$1 ≤ A_{i} ≤ 10^{3}$ for each valid $i$
$A_{1} + A_{2} + \ldots + A_{N} ≤ 10^{9}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3

5

1 2 3 4 5

4

5 4 3 6

10

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
----- Sample Output 1 ------ 
3

Impossible

1
----- explanation 1 ------ 
Example case 1: Stealing the third coin does not change the mean. Initially, it is $(1+2+3+4+5)/5 = 3$ and after stealing this coin, it is still $(1+2+4+5)/4 = 3$.

Example case 2: It is not possible to steal any coin without changing the mean.

Example case 3: The mean is always $10^{9}$, both initially and after removing any coin, so each coin can be stolen. In that case, we should choose the first coin.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Complete search


Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = sum(l) / len(l)
	if a in l:
		print(l.index(a) + 1)
	else:
		print('Impossible')


n = int(input())
for i in range(n):
	x = int(input())
	l = [int(j) for j in input().split()]
	s = sum(l)
	a = s / x
	c = 0
	for j in l:
		t = (s - j) / (x - 1)
		if a == t:
			c = l.index(j) + 1
			break
	if c != 0:
		print(c)
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	l = list(map(float, input().split()))
	m = sum(l) / n
	if m not in l:
		print('Impossible')
		continue
	for i in range(n):
		if l[i] == m:
			print(i + 1)
			break


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum2 = sum(a) / n
	for i in range(n):
		if a[i] == sum2:
			print(i + 1)
			break
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	(sum, index) = (0, 0)
	for i in arr:
		sum += i
	avg = sum / n
	if avg == int(avg) and avg in arr:
		for i in range(n):
			if avg == arr[i]:
				index = i + 1
				break
		print(index)
	else:
		print('Impossible')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	currmean = total / n
	flag = -1
	for i in range(n):
		if currmean == (total - a[i]) / (n - 1):
			print(i + 1)
			flag = 1
			break
	if flag == -1:
		print('Impossible')


n = int(input())
for i in range(n):
	x1 = int(input())
	lst = [int(j) for j in input().split()]
	s = sum(lst)
	an = s / x1
	c = 0
	for j in lst:
		y = (s - j) / (x1 - 1)
		if an == y:
			c = lst.index(j) + 1
			break
	if c != 0:
		print(c)
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	su = sum(li)
	val = su / n
	c = 0
	val1 = 1
	for i in range(len(li)):
		if (su - li[i]) / (n - 1) == val:
			c = i
			val1 = 0
			break
	if val1 == 1:
		print('Impossible')
	else:
		print(c + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	if s % n == 0:
		k = s // n
		if k in l:
			i = l.index(k)
			print(i + 1)
		else:
			print('Impossible')
	else:
		print('Impossible')


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	avg = sum(L) / N
	pos = -1
	for i in range(N):
		if L[i] == avg:
			pos = i
			break
	if pos == -1:
		print('Impossible')
	else:
		print(pos + 1)


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	m = sum(l) / x
	for i in range(x):
		if m == l[i]:
			print(i + 1)
			break
	else:
		print('Impossible')


t = int(input())
for i in range(t):
	n = int(input())
	coins = input().split(' ')
	for j in range(n):
		coins[j] = int(coins[j])
	mean = sum(coins) / n
	stole_coin = sum(coins) - mean * (n - 1)
	for x in range(n):
		if stole_coin == coins[x]:
			print(x + 1)
			break
	else:
		print('Impossible')


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = sum(a) / n
	for j in a:
		if m == j:
			x = a.index(j) + 1
			print(x)
			break
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) % n != 0:
		print('Impossible')
	else:
		m = sum(l) // n
		if m not in l:
			print('Impossible')
		else:
			print(l.index(m) + 1)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	mean = sum(l) / n
	for x in range(n):
		if l[x] == mean:
			print(x + 1)
			break
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ind = sum(lis) / n
	if ind in lis:
		print(lis.index(ind) + 1)
	else:
		print('Impossible')


t = int(input())
yu = []
for ml in range(0, t):
	gp = int(input())
	hh = str(input())
	pr = 0
	oli = hh.split(' ')
	kk = []
	for jre in oli:
		pr += int(jre)
		kk.append(int(jre))
	yur = pr / gp
	ird = [kk, yur]
	yu.append(ird)
for cc in yu:
	me = cc[1]
	tvc = cc[0]
	tcx = None
	vali = None
	for bbvc in range(0, len(tvc)):
		if tvc[bbvc] == me:
			if tcx == None:
				tcx = tvc[bbvc]
				vali = bbvc + 1
			elif tvc[bbvc] < tcx:
				tcx = bbvc
				vali = bbvc + 1
	if tcx == None:
		print('Impossible')
	else:
		print(vali)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mean = sum(arr) / n
	if mean not in arr:
		print('Impossible')
	else:
		print(arr.index(mean) + 1)


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	mean = sum(L) / N
	if mean not in L:
		print('Impossible')
	else:
		print(L.index(mean) + 1)


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = sum(li)
	m = s / n
	flag = 0
	ans = 0
	for i in range(n):
		r = s - li[i]
		ar = r / (n - 1)
		if ar == m:
			flag = 1
			ans = i + 1
			break
		r = 0
	if flag == 1:
		print(ans)
	else:
		print('Impossible')


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	mean = sum(a) / n
	if mean in a:
		print(a.index(mean) + 1)
	else:
		print('Impossible')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()[:n]))
	av = sum(l) / n
	if av in l:
		print(l.index(av) + 1)
	else:
		print('Impossible')


t = int(input())
for i in range(1, t + 1):
	n = int(input())
	l1 = list(map(int, input().split()[:n]))
	x = sum(l1) / n
	if x in l1:
		print(l1.index(x) + 1)
	else:
		print('Impossible')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	sm = sum(l) / len(l)
	newsm = sm * (n - 1)
	diff = sum(l) - newsm
	if diff in l:
		print(l.index(int(diff)) + 1)
	else:
		print('Impossible')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mean = sum(l) / n
	for i in range(n):
		if l[i] == mean:
			print(i + 1)
			break
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a) / n
	c = 0
	for i in range(n):
		if s == a[i]:
			print(i + 1)
			break
	else:
		print('Impossible')


import numpy as np
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	o = np.mean(l)
	k = []
	for i in l:
		if o == i:
			k.append(i)
	if len(k) == 0:
		print('Impossible')
	else:
		print(l.index(min(k)) + 1)


t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	sumarr = sum(arr)
	mean = sumarr / n
	flag = False
	for i in range(n):
		if mean == arr[i]:
			print(i + 1)
			flag = True
			break
	if flag == False:
		print('Impossible')
	t -= 1


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = []
	d = {}
	s = sum(arr)
	m = s / n
	for i in range(len(arr)):
		a = s - arr[i]
		m1 = a / (len(arr) - 1)
		if m1 == m:
			l.append(arr[i])
	if len(l) == 0:
		print('Impossible')
	else:
		k = l[0]
		if len(l) > 0:
			print(arr.index(k) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += l[i]
	m = s / n
	for i in range(n):
		if l[i] == m:
			idx = i
			break
	if m in l:
		print(idx + 1)
	else:
		print('Impossible')


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	kmap = {}
	tot = 0
	for (i, ele) in enumerate(arr):
		tot += ele
		if ele not in kmap:
			kmap[ele] = i
	reqtot = tot / n * (n - 1)
	diff = tot - reqtot
	if diff in kmap:
		print(kmap[diff] + 1)
	else:
		print('Impossible')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	mean = total / n
	ans = 'x'
	for i in range(n):
		if (total - a[i]) / (n - 1) == mean:
			ans = i + 1
			break
	print('Impossible' if ans == 'x' else ans)


for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	s = sum(a)
	mean = s / n
	flag = False
	for i in range(n):
		if s - a[i] == (n - 1) * a[i]:
			flag = True
			break
	if flag:
		print(i + 1)
	else:
		print('Impossible')


for _ in range(int(input())):
	x = int(input())
	l = list(map(float, input().split()))
	a = sum(l) / x
	if a in l:
		print(l.index(a) + 1)
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = sum(l) / n
	for i in range(len(l)):
		if l[i] == k:
			print(i + 1)
			break
	else:
		print('Impossible')


n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	k = sum(l) / a
	for j in range(a):
		if l[j] == k:
			print(j + 1)
			break
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	c = [float(x) for x in input().split()]
	sc = sum(c) / n
	if sc in c:
		for i in range(n):
			if c[i] == sc:
				print(i + 1)
				break
	else:
		print('Impossible')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	avg = sum(a) / n
	if avg in a:
		print(a.index(avg) + 1)
	else:
		print('Impossible')


def main():
	T = int(input())
	assert T >= 1 and T <= 10
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split()))[:N]
		avg = sum(A) / N
		for i in range(N):
			if A[i] == avg:
				print(i + 1)
				break
		else:
			print('Impossible')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = sum(a)
	me = x / n
	me2 = (n - 1) * me
	if x - me2 in a:
		print(a.index(x - me2) + 1)
	else:
		print('Impossible')


def CC():
	my_inputt = int(input())
	for _ in range(my_inputt):
		my_inputn = int(input())
		my_inputarr = list(map(int, input().split()))
		my_inputs = sum(my_inputarr)
		mean = my_inputs / my_inputn
		if mean in my_inputarr:
			print(my_inputarr.index(mean) + 1)
		else:
			print('Impossible')
CC()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = sum(l)
	c = k / n
	if c in l:
		print(l.index(c) + 1)
	else:
		print('Impossible')


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	sum1 = sum(list1)
	average = sum1 / n
	if average in list1:
		print(list1.index(average) + 1)
	else:
		print('Impossible')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = sum(a)
	mean = x / n
	flag = 0
	for i in a:
		if (x - i) / (n - 1) == mean:
			print(a.index(i) + 1)
			flag = 1
			break
	if flag == 0:
		print('Impossible')


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	num = sum(a) / n
	if int(num) in a and num.is_integer():
		print(a.index(int(num)) + 1)
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	m = s / n
	f = 0
	for i in range(n):
		if (s - a[i]) / (n - 1) == m:
			f = 1
			print(i + 1)
			break
	if f == 0:
		print('Impossible')


from statistics import mean
for t in range(int(input())):
	input()
	ai = [int(i) for i in input().split()]
	m = mean(ai)
	for i in range(len(ai)):
		if ai[i] == m:
			print(i + 1)
			break
	else:
		print('Impossible')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mean = sum(arr) / n
	for i in range(n):
		if arr[i] == mean:
			print(i + 1)
			break
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	q = sum(lst) / n
	if q == int(q):
		if q in lst:
			print(lst.index(q) + 1)
		else:
			print('Impossible')
	else:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	temp = 0
	s1 = sum(nums) / n
	for i in range(n):
		if s1 == nums[i]:
			print(i + 1)
			temp = 1
			break
	if temp == 0:
		print('Impossible')


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	sum1 = sum(l1)
	x = (sum1 * n - sum1 * (n - 1)) / n
	if x in l1:
		print(l1.index(x) + 1)
	else:
		print('Impossible')