B. 最短距离

内存限制:256 MiB 时间限制:1000 ms 输入文件: zdjl.in 输出文件: zdjl.out
题目类型:传统 评测方式:文本比较

题目描述

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

输入格式

第一行首先包含一个整数 N ,接下来包含 N 个整数 D_1,D_2,…,D_N ,其中 D_i 是第 i 个出口与第 i+1 个出口之间的距离, D_N 是第 N 个出口与第 1 个出口之间的距离。

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

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

输出格式

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

样例

输入样例:

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

输出样例:

3
10
7

数据范围与提示

80%数据: 3≤N≤10^5 1≤M≤10^4

100%数据: 3≤N≤10^5 1≤M≤2*10^5

高速公路总长度不超过 10^7