Haybale Distribution

Farmer John is distributing haybales across the farm!

Farmer John's farm has $N$ $(1 \leq N \leq 2 \cdot 1 0^{5})$ barns, located at integer points $x_{1}, \dots, x_{N}$ $(0 \leq x_{i} \leq 1 0^{6})$ on the number line. Farmer John's plan is to first have $N$ shipments of haybales delivered to some integer point $y$ $(0 \leq y \leq 1 0^{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 \leq a_{i}, b_{i} \leq 1 0^{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

{a_{i} \cdot (y - x) b_{i} \cdot (x - y) if y \geq x if x > y .

Given $Q$ $(1 \leq Q \leq 2 \cdot 1 0^{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.

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 \leq 10$
Input 3: $N, Q \leq 500$
Inputs 4-6: $N, Q \leq 5000$
Inputs 7-16: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

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

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

Submit

Language