题目描述

\(\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\)