环形公路出口

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

时间限制：1000

内存限制：65536

输入

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

输出

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

样例输入

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

样例输出

3
10
7