题目描述 一条环形高速公路有N个出口，给定任意一对出口，请你算出这两个出口的最短距离。 输入 输入第一行给出区间[3,10^5]内的整数N，以及N个整数距离D1D2...DN，其中Di是第i和第i+

题目描述

一条环形高速公路有N个出口，给定任意一对出口，请你算出这两个出口的最短距离。SO5100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

输入第一行给出区间[3,10^5]内的整数N，以及N个整数距离D1D2...DN，其中Di是第i和第i+1个出口之间的距离，DN是第N和第1个出口之间的距离。同行数字间以空格分隔。第二行给出正整数M(≤10^4)。随后M行，每行给出一对出口的编号(出口从1到N顺序编号)。题目保证公路全长不超过10^7。

输出

输出M行，每行给出对应输入的一对出口之间的最短距离。

数据范围

3≤N≤10^5,M≤10^4,公路全长不超过10^7

输入样例

5 1 2 4 14 9 3 1 3 2 5 4 1

输出样例

3 10 7