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' = V+1~). Then, each ~A_i~ greater than or equal to ~V'~ contributes ~-1~ to the change in the sum while each ~A_i~ less than ~V'~ contributes ~1~ to the change in the sum, so the change in this sum equals [number of elements less than ~V'~] minus [number of elements greater than or equal to ~V'~]. As ~v = -\infty \to \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'~ is greater than or equal to the number of elements greater than or equal to ~V'~. This happens at the median.