Bob 和他的好朋友们手拉手在一起围成了一个圈，给出每条边的权值，定义任意两个人的距离为他们之间的权值总和乘上他们的边数（由于成环，左右都可以走，取小的 作为距离）。
输入 k 组朋友，输出他们之间的距离分别是多少。
输入第一行为 n，代表总共有 n 个小朋友（编号为 1~n）。
输入第二行有 n 个非负整数，第一个代表 1 号和 2 号的距离，第二个代表 2 号和 3 号的距离，第 n 个代表 n 号和 1 号的距离。
输入第三行为 k，代表总共有 k 组查询。
接下来 k 行，每行有两个小于 n 的整数 x 和 y，代表查询 x 和 y 之间的距离。（x 和 y 可能相同）
共 k 行，每行一个数字，代表小朋友之间的距离。
【样例1】
5
84 43 1 96 63
1
1 4
【样例2】
5
91 92 27 54 46
1
2 2
【样例3】
5
98 41 53 65 76
1
3 2
【样例1】
318
【样例2】
0
【样例3】
41
样例 1：对于 1 号和 4 号小朋友，最短距离应该是 4->5->1 (96+63)*2=318
因为 1->2->3->4 (84+43+1)*3=384 取 318
样例 2：对于 2 号和 2 号小朋友，最短距离应该是 0
样例 3：对于 3 号和 2 号小朋友，最短距离应该是 3->2 41
对于 30% 的数据，满足 n<=5, k=1
对于 50% 的数据，满足 n<=10, k<=10
对于 70%的数据，满足 n<=100, k<=100
对于 100% 的数据，满足 n<=10000, k<=1000000