Description

一个环形高速公路上有 N 个出口，共有 M 次询问，

每次询问你需要回答其中两个出口之间的最短距离是多少。

Input Format

第一行首先包含一个整数 N，接下来包含 N 个整数 D1, D2, …, DN，

其中 Di是第 i 个出口与第 i+1 个出口之间的距离，DN是第 N 个出口与第 1 个出口之间的距离。

第二行包含一个整数 M，表示询问次数。

接下来 M 行，每行包含两个整数，表示询问两个出口之间的最短距离。

Output Format

共 M 行，每行输出一个查询的答案。

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

3
10
7

Hint

数据范围

3 ≤ N ≤ 105,

1 ≤ M ≤ 104,

高速公路总长度不超过 107。

Source