Haybale Distribution

Farmer John is distributing haybales across the farm.

Farmer John's farm has $N$ barns ($1\le N\le 2\cdot 10^5$), 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. 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 a shipment travels left, and $b_i$ haybales are wasted per unit of distance it travels right. For a shipment transported from point $y$ to a barn at point $x$, the number of haybales wasted is

$\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 giving a pair $(a_i,b_i)$ of possible values, determine the fewest haybales that will be wasted if Farmer John chooses $y$ optimally.

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