Subtask 1

It suffices to iterate over all possible minimizing values and determine the minimizing one.

Time Complexity: $\mathcal{O}((max(A_i)-min(A_i))N)$

Subtask 2

Realize that the sum of convex functions is convex.

Now, binary search for the minimizing point, $x$, by comparing the result from using $x$ compared to $x+1$:

• If $x$'s result is smaller than $x+1$'s, constrain the search to the left of $x$.
• If $x+1$'s result is smaller than $x$'s, constrain the search to the right of $x+1$.

Finally, output the minimizing value.

Alternative Solution

Note that the median of the array is always a minimizing value.

Consider what happens to the sum of $|V-A_i|$ when we increase $V$ by one (i.e., let $V^{\prime }=V+1$). Then, each $A_i$ greater than or equal to $V^{\prime }$ contributes $-1$ to the change in the sum while each $A_i$ less than $V^{\prime }$ contributes $1$ to the change in the sum, so the change in this sum equals [number of elements less than $V^{\prime }$] minus [number of elements greater than or equal to $V^{\prime }$]. As $v=-\mathrm{\infty }\to \mathrm{\infty }$, this change slowly goes from negative to positive; we wish to stop when this change becomes positive, that is, when the number of elements less than $V^{\prime }$ is greater than or equal to the number of elements greater than or equal to $V^{\prime }$. This happens at the median.