Problem Description

Farmer John is distributing haybales on his farm.

There are $N$ barns $(1 \le N \le 2 \cdot 10^5)$ on Farmer John’s farm, located at integer points $x_1,\ldots,x_N$ on a number line $(0 \le x_i \le 10^6)$. Farmer John plans to transport $N$ truckloads of haybales to an integer point $y$ $(0 \le y \le 10^6)$, and then deliver one truckload to each barn.

Unfortunately, Farmer John’s delivery system wastes many haybales. Specifically, given some $a_i, b_i$ $(1 \le a_i, b_i \le 10^6)$, for each truckload, moving one unit distance to the left wastes $a_i$ haybales, and moving one unit distance to the right wastes $b_i$ haybales. Formally, for one truckload moving from integer point $y$ to a barn at position $x$, the number of wasted haybales is:

$$\begin{cases}a_i\cdot (y-x) & \text{if} \ y>x \\ b_i\cdot(x-y)&\text{if}\ x>y\end{cases}$$

You are given $Q$ independent queries $(1 \le Q \le 2 \cdot 10^5)$. Each query provides a pair $(a_i, b_i)$. Help Farmer John compute, when choosing the best $y$, the minimum total number of haybales wasted.

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, b_i$.

Output Format

Output $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

5
1 4 2 3 10
4
1 1
2 1
1 2
1 4

11
13
18
30

Hint

Sample Explanation 1

In the second query of the sample, the best choice is $y = 2$. The number of wasted haybales is $2(2-1) + 2(2-2) + 1(3-2) + 1(4-2) + 1(10-2) = 2 + 0 + 1 + 2 + 8 = 13$.

Test Point Properties

• Test point $2$ satisfies $N, Q \le 10$.
• Test point $3$ satisfies $N, Q \le 500$.
• Test points $4-6$ satisfy $N, Q \le 5000$.
• Test points $7-16$ have no additional constraints.

Translated by ChatGPT 5