Description

晨晨最近对一组数中某一段数的和很感兴趣，她想编一道程序，已知一组数，只要输入开始位置s和结束位置e，就能输出这段范围内的数之和。

Input Format

第一行，n，表示有n个整数。(n<=1000000)

第二行，n个1000以内的整数。

第三行，m，表示有m次询问。（1<=m<=100000)

接下来m行，每行两个数，表示开始和结束的位置。(1<=s<=e<=n)

Output Format

m行，每行一个数，表示每次询问的答案。

10
5 3 2 1 4 5 3 6 9 12
2
2 4
3 5

6
7