卷王xzy / 【模板】前缀和

卷王xzy / 【模板】前缀和

题目描述

\(\text{XzyStudio}\) \(dalao\) 十分内卷,他每天都会 AK 若干比赛。现在,我们最聪明的 \(Baka\) 想知道在一段时间内,xzy 到底打了多少比赛。

输入输出格式

输入格式

第一行,为一个正整数 \(n\),表示天数。
第二行,为 \(n\) 个正整数 \(a_1, a_2, \dots, a_n\),其中,\(a_i\) 表示在第 \(i\) 天 xzy AK 的比赛数量。
第三行,为一个正整数 \(m\),表示 \(Baka\) 的询问次数。
接下来 \(m\) 行,每行两个正整数 \(l_i, r_i(1 \le l_i \le r_i \le n)\),表示询问在第 \(l_i\) 到 \(r_i\) 天内,xzy 一共 AK 了多少场比赛。

输出格式

共 \(m\) 行,第 \(i\) 行表示第 \(i\) 组询问的答案。

样例

输入

5
5 3 4 2 6
3
1 3
3 5
2 3

输出

12
12
7

数据范围

对于 \(50 \%\) 的数据,\(1 \le n, m \le 1000\);
对于 \(100 \%\) 的数据,\(1 \le n, m \le 10^5, 1 \le a_i \le 10^4\)
\(\color{white}XzyStudio\ tql\ orz\ orz\ orz\)

信息

ID
1050
难度
9
分类
(无)
标签
(无)
递交数
5
已通过
3
通过率
60%
被复制
1
上传者

相关

在下列训练计划中:

模板 | Templates