P9982 [USACO23DEC] Haybale Distribution G

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.

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 $Q$ lines. The $i$-th line contains the answer to the $i$-th query.

### 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