CF2169A Alice and Bob

Alice and Bob have a bag with $ n $ marbles, with the integer $ v_i $ written on the $ i $ -th marble. They play the following game: first, each player chooses an integer (let's denote the integer chosen by Alice as $ a $ , and the integer chosen by Bob as $ b $ ). After that, they start drawing marbles from the bag in any order until the bag is empty. For each ball, the point goes to the one whose chosen integer is closer to the integer on the marble; in case of a tie, Alice gets the point. For example, if $ a = 10 $ , $ b = 30 $ , then - for marbles with integers $ 10, 1, 7, 18, 20 $ , and many others, Alice gets the points (note that she will get a point for the marble $ 20 $ ); - for marble with integer $ 59, 25, 30, 21 $ , and many others, Bob gets the points. Bob has managed to find out in advance which integer Alice will choose. Help him to choose his integer in such a way as to maximize the number of points he receives.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines: - The first line contains two integers $ n $ and $ a $ ( $ 1 \le n \le 3 \cdot 10^5 $ ; $ 1 \le a \le 10^9 $ ) — the number of marbles in the bag and the number chosen by Alice, respectively. - The second line contains $ n $ integers $ v_1, v_2, \dots, v_n $ ( $ 1 \le v_1 \le v_2 \le \dots \le v_n \le 10^9 $ ). Additional constraint on the input: the sum of $ n $ across all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output a single integer $ b $ ( $ 0 \le b \le 2 \cdot 10^9 $ ) that Bob should choose to maximize the number of points he receives. If there are multiple such numbers, you may output any of them.

In the first test case, if Bob chooses $ 35 $ , he gets $ 5 $ points for marbles $ 30, 40, 50, 60, 70 $ . In the third test case, no matter which integer Bob chooses, he gets $ 0 $ points.