Omar is an AI engineer who is studying statistics. Recently, he knew about $$$mean$$$ and $$$median$$$.
His curiosity makes him wonder, if you have an array $$$a$$$ of $$$n$$$ integers, can you add just one integer $$$\bf{X}$$$ such that the $$$mean$$$ and the $$$median$$$ of the updated array would be equal?
Where the $$$mean$$$ of an array $$$a$$$ equals: $$$\frac{\sum_{i = 1}^n a_i}{n}$$$. The $$$mean$$$ of the array $$$[2, 6, 1, 2, 4]$$$ is $$$\frac{2+6+1+2+4}{5} = 3$$$.
A $$$median$$$ of an array of $$$n$$$ numbers is the element which occupies position number $$$\lfloor \frac{n+1}{2} \rfloor$$$ after we sort the elements in the non-decreasing order (the array elements are numbered starting from 1). The $$$median$$$ of the array $$$[2, 6, 1, 2, 3]$$$ is $$$2$$$, and the $$$median$$$ of the array $$$[0, 96, 17, 23]$$$ is 17.
We define an expression $$$\lfloor \frac{a}{b} \rfloor$$$ as the integer part of dividing number $$$a$$$ by number $$$b$$$.
It's guaranteed that The answer is always exists under the given constraints
The first line contains $$$1 \le T \le 1000$$$ number of test cases.
For each test case, you will be given an integer $$$1 \le n \le 10^6$$$ followed by $$$n$$$ integers $$$-10^9 \le a_i \le 10^9$$$.
It is guaranteed that the sum of n over all test cases doesn't exceed $$$10^6$$$.
For each test case, you have to print one integer $$$\bf{X}$$$ that solves the problem.
If there are multiple solutions print the minimum one.
222 351 2 3 4 6
1 -4
In the first test case, the updated array will be [1, 2, 3], $$$mean$$$ = $$$median$$$ = 2.
In the second test case, the updated array will be [-4, 1, 2, 3, 4, 6], $$$mean$$$ = $$$median$$$ = 2.
Name |
---|