Фермер Джон развозит сено по ферме.
Ферма имеет \(N\) \((1\le N\le 2\cdot 10^5)\) амбаров, расположенных в целых точках
\(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\) на числовой прямой. ФД запланировал
\(N\) перевозок сена в некоторую целую точку \(y\) \((0 \le y \le 10^6)\) и затем
одну перевозку к каждому амбару.
К несчастью служба доставки очень расточительна. В частности,
для некоторых \(a_i\) и \(b_i\) \((1\le a_i, b_i\le 10^6)\), \(a_i\) пакетов сена
теряются на единицу расстояния каждой доставки влево и \(b_i\) пакетов сена
теряются на единицу расстояния каждой доставки вправо.
Формально при транспортировке из точки \(y\) в амбар в точке \(x\),
количество теряемых пакетов сена определяется как
\[\begin{cases}
a_i\cdot (y-x) & \text{if } y \ge x \\
b_i\cdot (x-y) & \text{if } x > y
\end{cases}.\]
Вам даны \(Q\) \((1\le Q\le 2\cdot 10^5)\) независимых запросов, каждый состоит
из возможных значений \((a_i,b_i)\), помогите ФД определить наименьшее количество
потерянных пакетов сена, если он выберет \(y\) оптимально.
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит
\(N\).
Следующая строка содержит \(x_1\dots x_N\).
Следующая строка содержит \(Q\).
Каждая из последующих \(Q\) строк содержит два целых числа \(a_i\) и \(b_i\).
ФОРМАТ ВЫВОДА (на экран):
Выведите \(Q\) строк, \(i\)-ая строка содержит ответ на \(i\)-ый запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4 2 3 10
4
1 1
2 1
1 2
1 4
|
11
13
18
30
|