#Z1025. 【深进1.例1】求区间和

【深进1.例1】求区间和

题目描述

给定 nn 个正整数组成的数列 a1,a2,,ana_1, a_2, \cdots, a_nmm 个区间 [li,ri][l_i,r_i],分别求这 mm 个区间的区间和。对于所有测试数据,n,m105,ai104n,m\le10^5,a_i\le 10^4

输入格式

n+m+2n+m+2 行。

第一行,为一个正整数 nn

第二行,为 nn 个正整数 a1,a2,,ana_1,a_2, \cdots ,a_n

第三行,为一个正整数 mm

44 到第 n+m+2n+m+2 行,每行为两个正整数 li,ril_i,r_i ,满足1lirin1\le l_i\le r_i\le n

输出格式

mm 行。

ii 行为第 ii 组答案的询问。

4
4 3 2 1
2
1 4
2 3
10
5

提示

样例解释:第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为5。

对于 50% 的数据:n,m1000n,m\le 1000

对于100% 的数据:n.m105,ai104n.m\le 10^5,a_i\le 10^4