Hints: Array

Fix an index $i$ and a candidate $k$. For $j > i$, you compare $|a_i - k|$ and $|a_j - k|$ on the number line. For $a_j \ne a_i$, when is the inequality $|a_i - k| > |a_j - k|$ equivalent to a half-line condition on $k$ (strictly on one side of the midpoint of $a_i$ and $a_j$)?

Answer to Hint 1: Let $m = \frac{a_i+a_j}{2}$. If $a_j > a_i$, both distances are affine to the right of $a_i$ and $a_j$; strict inequality holds for $k$ strictly to the right of $m$, i.e.\ $k \ge \left\lceil \frac{a_i+a_j+1}{2}\right\rceil$, which the model implements as $(a_i+a_j+2)/2$ in integer division. If $a_j < a_i$, you get the symmetric condition on the left: $k \le \left\lfloor \frac{a_i+a_j-1}{2}\right\rfloor$, i.e.\ $(a_i+a_j-1)/2$. If $a_j = a_i$, the strict inequality is impossible.

Answer to Hint 2: For fixed $i$, every $j$ with $a_j > a_i$ contributes a lower bound $L_j = (a_i+a_j+2)/2$; every $j$ with $a_j < a_i$ contributes an upper bound $R_j = (a_i+a_j-1)/2$. Choosing an integer $k$ satisfies $j$ iff $L_j \le k$ (left case) or $k \le R_j$ (right case).

Why is it enough to collect all $L_j$ into one multiset L and all $R_j$ into R?

Answer to Hint 3: The constraints for different $j$ are independent: a single $k$ is counted for $j$ iff it lies in that $j$’s allowed ray. So the count for a fixed $k$ is the number of $j$ with $a_j > a_i$ and $L_j \le k$ plus the number of $j$ with $a_j < a_i$ and $k \le R_j$.

Answer to Hint 4: Sort L and R. For a candidate $k$, use upper_bound on L to count how many $L_j \le k$, and lower_bound on R to count how many $R_j \ge k$; add the two counts.

Why can the maximum over all integers $k$ be found by checking only finitely many candidate $k$?

Answer to Hint 5: As $k$ moves along $\mathbb{Z}$, the two counts change only when $k$ crosses values in L or R, so the total is piecewise constant between consecutive sorted values. Check every distinct value in L ∪ R, and also check $k = L_{\max}+1$ and $k = R_{\min}-1$ to catch intervals between breakpoints (as in the model).

Answer to Hint 6: For each test case, loop $i = 0..n-1$, build L and R, dedupe sorted candidates, evaluate each candidate in $O(\log n)$, take the maximum, and output the array of answers.