Haybale Distribution

문제

Farmer John is distributing haybales across the farm!

Farmer John's farm has $NN$ $(1\le N\le 2\cdot {10}^5)(1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5)$ barns, located at integer points $x_1,\dots ,x_{N}x\_1,\backslash dots,\; x\_N$ $(0\le x_i\le {10}^6)(0\; \backslash le\; x\_i\; \backslash le\; 10^6)$ on the number line. Farmer John's plan is to first have $NN$ shipments of haybales delivered to some integer point $yy$ $(0\le y\le {10}^6)(0\; \backslash le\; y\; \backslash 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}a\_i$ and $b_{i}b\_i$ $(1\le a_i,b_i\le {10}^6)(1\backslash le\; a\_i,\; b\_i\backslash le\; 10^6)$, $a_{i}a\_i$ haybales are wasted per unit of distance left each shipment is transported, and $b_{i}b\_i$ haybales are wasted per unit of distance right each shipment is transported. Formally, for a shipment being transported from point $yy$ to a barn at point $xx$, the number of haybales wasted is given by

Given $QQ$ $(1\le Q\le 2\cdot {10}^5)(1\backslash le\; Q\backslash le\; 2\backslash cdot\; 10^5)$ independent queries each consisting of possible values of $(a_i,b_i)(a\_i,b\_i)$, please help Farmer John determine the fewest amount of haybales that will be wasted if he chooses $yy$ optimally.

입력

The first line contains $NN$.

The next line contains $x_1\dots x_{N}x\_1\backslash dots\; x\_N$.

The next line contains $QQ$.

The next $QQ$ lines each contain two integers $a_{i}a\_i$ and $b_{i}b\_i$.

출력

Output $QQ$ lines, the $ii$th line containing the answer for the $ii$th query.

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

11
13
18
30