【知识点】
我们现在有一个数组为 $[1,\ 8,\ 3,\ 4,\ 7,\ 1,\ 6,\ 2]$，我们需要查询 $[1,\ 6]$ 这个区间，如下图所示。

我们可以发现，其实在每次查询的时候，是不断对当前层级所表示的区间进行二分分治，直到最后每个分块的并集即为待查询区间。
我们需要查询 $[L,\ R]$ 区间的数据和，也就是 $\sum_{i=L}^{R}a_i$。
如上图所示的动画中，我们只需要查询 $[1,\ 4]$ 和 $[5,\ 6]$ 这两个区间即可。这样我们得到区间和为 $16+8=24$。

【任务要求】
完成本任务，我们将学会使用查询区间和操作。

第一行包括 $1$ 个整数 $n\ (1≤n≤10^4)$，表示数组 $a$ 的大小。
第二行包括 $n$ 个数字，每个数字 $−10^4≤a_i≤10^4$。两个数字用空格隔开。
第三行包括 $1$ 个整数 $m\ (1≤m≤10^5)$，表示 $m$ 个查询。
第 $4 \sim 4+m−1$ 行，每行包括 $2$ 个整数 $L,\ R\ (1 \leq L \leq R \leq n)$，第一个整数 $L$ 表示查询的起点，第二个整数 $R$ 表示查询的终点。

$m$ 行，每行 $1$ 个整数，表示从 $[L,\ R]$ 之间元素和。