题目描述

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

input

5
84 43 1 96 63
1
1 4

output

318

样例 1： 对于 1 号和 4 号小朋友，最短距离应该是 4->5->1 (96+63)2=318 因为 1->2->3->4 (84+43+1)3=384 取 318

样例数据2

input

5
91 92 27 54 46
1
2 2

output

0

对于 2 号和 2 号小朋友，最短距离应该是 0

样例数据3

input

5
98 41 53 65 76
1 
3 2

output

41

对于 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