问题描述

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

Format

Input

第一行首先包含一个整数 𝑁，接下来包含 N个整数 D，其中 Di 是第 𝑖 个出口与第i+1 个出口之间的距离，DN 是第 N 个出口与第 1 个出口之间的距离。 第二行包含一个整数 𝑀，表示询问次数。 接下来 𝑀 行，每行包含两个整数，表示询问两个出口之间的最短距离。

Output

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

Samples

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

3
10
7

Limitation

3≤𝑁≤10^5, 1≤𝑀≤10^4, 高速公路总长度不超过 10^7 。