环形补给线
时间限制:1 s 内存限制:256 MB
题目背景
罗德岛本舰的外围有一条环形补给公路,沿顺时针方向分布着 n 个补给站,编号 1∼n。第 i 个补给站存放 ai 份物资。
公路是环形的,所以从 l 号站沿顺时针走到 r 号站,不一定只经过编号 l,l+1,…,r 的站:如果 l>r,还会先经过 n 号站,再回到 1 号站。
凯尔希给了博士 q 次查询。每次给出 l,r,博士想知道:从 l 号站顺时针走到 r 号站(包含起点和终点),一共能收集多少份物资?
输入格式
第一行两个整数 n,q。
第二行 n 个整数 a1,a2,…,an。
接下来 q 行,每行两个整数 l,r。
输出格式
输出 q 行,每行一个整数,表示对应查询的答案。
样例
样例输入 #1
5 3
2 3 5 7 11
1 3
4 2
3 3
`
### 样例输出 #1
```text
10
23
5
样例解释
- 1→3:经过 1,2,3 号站,物资为 2+3+5=10。
- 4→2:经过 4,5,1,2 号站,物资为 7+11+2+3=23。
- 3→3:只经过 3 号站,物资为 5。
数据范围
- 对于 20% 的数据,1≤n,q≤10。
- 对于 50% 的数据,1≤n,q≤1000。
- 对于 100% 的数据,1≤n,q≤105,0≤ai≤109,1≤l,r≤n。
提示
- l≤r 时,答案就是普通区间和。
- l>r 时,可以拆成 [l,n] 和 [1,r] 两段,也可以用“总和减去没有走到的那一段”。
- 答案可能超过
int,请使用 long long。