一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。
输入第一行给出区间 [3,] 内的整数 N,以及 N 个整数距离 ,其中 是第 i 和第 i+1 个出口之间的距离, 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。
第二行给出正整数 M ()。随后 M 行,每行给出一对出口的编号(出口从 1 到 N 顺序编号)。题目保证公路全长不超过 。
输出 M 行,每行给出对应输入的一对出口之间的最短距离。
样例输入
5 1 2 4 14 9 3 1 3 2 5 4 1
样例输出
3 10 7