环形公路出口

题目描述

一条环形高速公路有N个出口，给定任意一对出口，请你算出这两个出口的最短距离。

输入

输入第一行给出区间[3,10^5]内的整数N，以及N个整数距离 D¹,D²,,,,,,D^N，其中Dⁱ 是第i和第i+1个出口之间的距离，D^N是第N和第1个出口之间的距离。同行数字间以空格分隔。

第二行给出正整数M(≤10^4)。随后M行，每行给出一对出口的编号(出口从1到N顺序编号)。

题目保证公路全长不超过10^7。

输出

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

输入样例

5 1 2 4 14 9

3

1 3

2 5

4 1

输出样例

3

10

7