Alice and Bob

We need choose Bob's integer $b$ to maximize how many marbles are closer to $b$ than to Alice's fixed integer $a$.

The important detail is the tie rule: if a marble is exactly equally close to both numbers, Alice gets it. So Bob needs a strictly smaller distance.

For a marble value $x$, Bob scores it iff

$$|x-b| < |x-a|.$$

What if Bob chooses $b>a$?

Then Alice is on the left, Bob is on the right. The boundary between them is the midpoint:

$$\frac{a+b}{2}.$$

Bob wins values strictly to the right of that midpoint:

$$2x > a+b.$$

Now here's the whole trick: if Bob moves $b$ farther right, then $a+b$ increases, so the midpoint moves right, and Bob can only win fewer marbles. Moving farther away does not magically help. It just drags the boundary away from Alice. Classic overthinking trap.

So if Bob wants to win right-side marbles, the best possible choice is the closest integer to the right:

$$b = a+1.$$

Then Bob wins all integer marble values $x$ satisfying

$$2x > 2a+1,$$

which is exactly

$$x > a.$$

So choosing $a+1$ gives Bob every marble greater than $a$.

What if Bob chooses $b<a$?

Symmetric story. Bob wins values strictly to the left of the midpoint:

$$2x < a+b.$$

To maximize this, Bob should choose the closest integer to the left:

$$b = a-1.$$

Then Bob wins all integer values $x$ satisfying

$$2x < 2a-1,$$

which is exactly

$$x < a.$$

So choosing $a-1$ gives Bob every marble less than $a$.

Can Bob ever win a marble equal to $a$?

Nope. If $x=a$, Alice's distance is $0$. Bob cannot beat distance $0$. If Bob also chooses $a$, it is a tie, and Alice still gets it. Those marbles are completely unwinnable for Bob. Sad little zeros.

So the entire problem reduces to:

• count marbles with value $<a$;
• count marbles with value $>a$;
• if the left count is bigger, output $a-1$;
• otherwise output $a+1$.

Both outputs are always valid: since $1 \le a \le 10^9$, we have $a-1 \ge 0$ and $a+1 \le 2 \cdot 10^9$.

The array is sorted, so we can use binary search:

• lower_bound(v.begin(), v.end(), a) gives the first index with value $\ge a$, so that index is the number of values $<a$;
• upper_bound(v.begin(), v.end(), a) gives the first index with value $>a$, so $n - index$ is the number of values $>a$.

The complexity is $O(\log n)$ per test case after reading the array, and reading all input already costs $O(n)$ total. Plenty fast.