It's Halloween! Graham the Ghost is very excited for this spooky celebration. Of course, Graham wants to maximize the number of sweets he snags from his neighborhood. Of course, he also asks you for help in planning these routes.

The neighborhood is made of ~N~ houses in a horizontal line. Each house can be represented by an integer ~i~ (~1 \leq i \leq N~) where the ~i~th house means the ~i~th house from the left. Each house has an integer ~C_i~, which represents the number of candies house ~i~ would give to Graham. You know this information from being an insider in the trick-or-treating industry.

However, top secret intel recently uncovered that every even-numbered house is cursed and will take candy from Graham instead of giving it! More precisely, house ~i~ will give Graham ~C_i~ candies if ~i~ is odd and take ~C_i~ candies from him if ~i~ is even.

Graham has ~Q~ ranges that he plans to trick-or-treat on, and in no small part due to the cursed houses he wants you to precalculate the candy he will get for each range. Can you help Graham make it out of this month without going into crippling candy debt?

Constraints

~1 \leq N \leq 2 \times 10^5~

~1 \leq Q \leq 2 \times 10^5~

~1 \leq C_i \leq 10^4~

Subtask 1 [30%]

~1 \leq N \leq 10^4~

~1 \leq Q \leq 10^4~

Subtask 2 [70%]

No additional constraints.

Input Specifications

The first line will contain ~N~, the number of houses.

The next line will contain ~N~ integers ~C_i~ (~1 \leq i \leq N~), the candy values for the houses

The next line will contain ~Q~, the number of ranges Graham wants to precalculate.

The next ~Q~ lines will contain two integers ~l, r~ (~1 \leq l \leq r \leq N~), the inclusive endpoints of the range. Note that ranges may overlap.

Output Specifications

Output ~Q~ lines, each containing one integer — the number of candies you will get when trick-or-treating at the houses in the specified range.

Sample Input

6
3 3 4 8 1 2
2
1 3
2 6

Sample Output

4
-8

Sample explanation

For the first query, Graham acquires ~3 - 3 + 4 = 4~ candies. For the second query, Graham acquires ~-3 + 4 - 8 + 1 - 2 = -8~ candies. Looks like he's going into debt...