2300: 最短距离

一个环形高速公路上有 N 个出口，共有 M次询问，每次询问你需要回答其中两个出口之间的最短距离是多少。

输入格式

第一行首先包含一个整数 N，接下来包含 N个整数 D1,D2,…,DN，其中 Di 是第 i 个出口与第 i+1 个出口之间的距离，DN是第 N出口与第 1 个出口之间的距离。

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

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

输出格式

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

数据范围

3≤N≤10^5
1≤M≤10^4
高速公路总长度不超过 10^7

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

3
10
7