gold_Haybale_Distribution (USACO December_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: sorting, prefix sum, mathematics, ternary search

Farmer John is distributing haybales across the farm!
Farmer John's farm has $N$ $(1\le N\le 2\cdot 10^5)$ barns, located at integer
points $x_1,\dots, x_N$ $(0 \le x_i \le 10^6)$ on the number line. Farmer John's
plan is to first have $N$ shipments of haybales delivered to some integer point
$y$ $(0 \le y \le 10^6)$ and then distribute one shipment to each barn.
Unfortunately, Farmer John's distribution service is very wasteful. In
particular, for some $a_i$ and $b_i$ $(1\le a_i, b_i\le 10^6)$, $a_i$ haybales
are wasted per unit of distance left each shipment is transported, and $b_i$
haybales are wasted per unit of distance right each shipment is transported.
Formally, for a shipment being transported from point $y$ to a barn at point
$x$, the number of haybales wasted is given by
$$\begin{cases}
 a_i\cdot (y-x) & \text{if } y \ge x \\
b_i\cdot (x-y) & \text{if } x > y
\end{cases}.$$
Given $Q$ $(1\le Q\le 2\cdot 10^5)$ independent queries each consisting of
possible values of $(a_i,b_i)$, please help Farmer John determine the fewest
amount of haybales that will be wasted if he chooses $y$ optimally.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $N$.
The next line contains $x_1\dots x_N$.
The next line contains $Q$.
The next $Q$ lines each contain two integers $a_i$ and $b_i$.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $Q$ lines, the $i$th line containing the answer for the $i$th query.
SAMPLE INPUT:
5
1 4 2 3 10
4
1 1
2 1
1 2
1 4
SAMPLE OUTPUT:
11
13
18
30
For example, to answer the second query, it is optimal to select $y=2$. Then the
number of wasted haybales is equal to
$2(2-1)+2(2-2)+1(3-2)+1(4-2)+1(10-2)=1+0+1+2+8=13$.
SCORING:
Input 2: $N,Q\le 10$
Input 3: $N,Q\le 500$
Inputs 4-6: $N,Q\le 5000$
Inputs 7-16: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: