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.
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.
You have to output Q integers, each denoting the answer to the corresponding query.
1 <= N <= 10^5 1 <= Q <= 10^5 1 <= L <= R <= N 1 <= A[i] <= 10^9