Description

Bob和他的好朋友们手拉手在一起围成了一个圈，给出每条边的权值，定义任意两个人的距离为他们之间的权值总和乘上他们的边数（由于成环，左右都可以走，取小的作为距离）。输入k组朋友，输出他们之间的距离分别是多少。

Input Format

输入第一行为n，代表总共有n个小朋友（编号为1~n）。
输入第二行有n个非负整数，第一个代表1号和2号的距离，第二个代表2号和3号的距离，第n个代表n号和1号的距离。
输入第三行为k，代表总共有k组查询。
接下来k行，每行有两个小于n的整数x和y，代表查询x和y之间的距离。（x和y可能相同）

Output Format

共k行，每行一个数字，代表小朋友之间的距离。

5
84 43 1 96 63
1
1 4

318

Hint

【输出输出样例1】

friend.in	friend.out
5 84 43 1 96 63 1 1 4	318

【输出输出样例2】

friend.in	friend.out
5 91 92 27 54 46 1 2 2	0

【输出输出样例3】

friend.in	friend.out
5 98 41 53 65 76 1 3 2	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

Source

模拟 贪心