Chef and Mean
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JULY19/hindi/CHFM.pdf), [Bengali](http://www.codechef.com/download/translated/JULY19/bengali/CHFM.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JULY19/mandarin/CHFM.pdf), [Russian](http://www.codechef.com/download/translated/JULY19/russian/CHFM.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JULY19/vietnamese/CHFM.pdf) 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 \le T \le 10$ - $2 \le N \le 10^5$ - $1 \le A_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (30 points):** - $2 \le N \le 10^3$ - $1 \le A_i \le 10^3$ for each valid $i$ - $A_1 + A_2 + \ldots + A_N \le 10^9$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 3 5 1 2 3 4 5 4 5 4 3 6 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ``` ### Example Output ``` 3 Impossible 1 ``` ### Explanation **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.
|Tags||cakewalk, july-challenge, july19, mishra_tanay_|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.