Array

Main Observation

Fix an index $i$ and call $x=a_i$. For a later value $y=a_j$, we need

$$|x-k|>|y-k|.$$

That means $k$ is closer to $y$ than to $x$. The boundary is their midpoint.

If $y>x$, then $y$ wins when

$$k>\frac{x+y}{2}.$$

If $y<x$, then $y$ wins when

$$k<\frac{x+y}{2}.$$

If $y=x$, it never wins, because the distances are always equal. Brutal, but fair.

Sweep The Value Of $k$

Imagine moving $k$ from very small to very large.

At $k=-\infty$, every later value $y<x$ is counted, and every later value $y>x$ is not counted.

When $k$ crosses the midpoint with some $y$:

• if $y<x$, that element stops being counted;
• if $y>x$, that element starts being counted;
• if $y=x$, nothing happens.

So for each fixed $i$, the answer is just the maximum active count during this sweep.

Since $x$ is fixed, the midpoint

$$\frac{x+y}{2}$$

is ordered the same way as $y$. Therefore we can sort the suffix values $a_{i+1},\ldots,a_n$ and process them in increasing order.

Algorithm

For each $i$:

1. Put all values $a_{i+1},\ldots,a_n$ into a vector $b$.
2. Sort $b$.
3. Initialize

$$cur=\#\{y\in b:y<a_i\}.$$

This is the count for very small $k$.

4. Sweep $b$ from smallest to largest:

$$cur \mathrel{+}= \begin{cases} -1,& y<a_i,\\ 0,& y=a_i,\\ +1,& y>a_i. \end{cases}$$

5. The maximum value seen is the answer for $i$.

The integer restriction on $k$ does not ruin this. The count only changes at midpoint thresholds, and the best sweep state can be achieved by choosing an integer $k$ sufficiently far left/right or between relevant threshold groups.

Complexity

For each $i$, sorting the suffix costs $O((n-i)\log n)$. Overall:

$$O(n^2\log n)$$

per test case, with $O(n)$ extra memory. Since

$$\sum n\le 5000,$$

this easily passes.