题目描述

在一条笔直的海岸线上有 n ( 1 <= n <= 2*105 )座灯塔，每座灯塔的位置分别为 ai ( 0 <= ai <= 106 )。

为了保障安全，需要给这些灯塔单独配置一个小型发电站，已知发电站可以建造在海岸线的任意位置（可以造在灯塔所在的位置），但是根据计算：

在发电站左边的灯塔所消耗的电量为 ：灯塔和发电站之间的距离 * 系数 x；

在发电站右边的灯塔所消耗的电量为 ：灯塔和发电站之间的距离 * 系数 y；

为了减少电能的消耗，需要选择最合理的位置，使得所有灯塔消耗的电能最小，请你计算一下，最少消耗的电能是多少。

输入

第一行，整数 n，为灯塔数量。

第二行，n 个整数 ai，表示每个灯塔的位置。

第三行，整数 m，表示有 m 次询问。

接下来 m 行，每行两个系数 x 和 y。

输出

m 行，每行一个结果，分别每次询问中不同的系数下的最少电能消耗。

样例输入 6

1 4 5 3 7 8

2

1 2

2 1

样例输出 17 16

提示

样例解析：

发电站可以建造在位置 5:

左边灯塔的电能消耗为 (5-1)*1 + (5-3)*2 + (5-4)*1 = 7；

右边灯塔的电脑消耗为 (7-5)*2 + (8-5)*2 = 10；

最终最少消耗为 7 + 10 = 17。

数据范围：

1 <= n , m <= 2*105。

0 <= ai <= 106 。

0 <= x , y <= 106 。