Nitin has been given an array A of N integers and now, he has to answer Q questions.
A question has two integers L and R and the answer to a particular query is:

F(L, R) = A[L] - A[L+1] + A[L+2] - A[L+3] + ... + A[R]*(-1)^(R-L)
But since Nitin is not sober, you have to answer all the questions for him.

Input Format:

The first line of input contains the value N. N denotes the size of array.
The next line contains N spaced integers. These N integers denote the array.
The next line contains the value Q which denotes the number of queries.
Then, Q lines follow each containing two integers L and R.

Output Format:

You have to output Q integers, each denoting the answer to the corresponding query.

Constraints:

1 <= N <= 10^5
1 <= Q <= 10^5
1 <= L <= R <= N
1 <= A[i] <= 10^9

Sample Input:

5
4 5 6 1 2
3
1 1
2 4
3 5

Sample Output:

4
0
7