Problem Setter: M M Mehedi Hasan

Intake 33, Department of CSE

Do you like chocolates? Maybe, or not, but my younger sister likes chocolates so much and she wants to buy more chocolates. Every day she comes to me with a list of chocolates of N types from 1 to N, where the price is given of every type of chocolates. Finally, she askes me what amount of money she will need if she wants to buy chocolates from L to R positions?

I heard that you are a good programmer of BUBT. So, you should write a program, which gives the total price of chocolates from L to R positions.

Input Format

In the first line, you are given one integer N (1 <= N <= 10⁵) denoting the total number of different chocolates. The second line contains N number of integers like as, P₁, P₂, P₃, ..., P_n. Here P_i  (1<=P_i<=10⁵)denotes the price of i^th chocolate.

In the third line, you are given one integer T (1 <= T <= 10⁵), which is the number of test cases. In each test case, you are given two integers L and R (1 <= L <= R <= N).

Output Format

You should write a program, which gives the total price of chocolates from position L to R for each test case. Print the output of each test case in a separate line.

Samples