You've discovered a magical candy van that has a single, long display of ~n~ candies in a row, found in the back of Oree's van. Each candy has a "flavour value" which can be a positive (sweet), negative (sour), or zero (tasteless).

Oree, a friendly wizard, offers you a special deal. You can choose any continuous section of candies from a starting position ~l~ to an ending position ~r~. The total flavour of your chosen section is the sum of the flavour values of all the candies from ~l~ to ~r~.

However, Oree adds a little magic bonus! If the total flavour of your chosen section is positive, you get an extra ~10~ bonus flavour points. If the total flavour is negative, you get a ~10~ point penalty (subtracting ~10~ from your total). If the total flavour is exactly zero, Oree will be so impressed that he gives you a ~100~ point bonus. You'll also get to ride in the back of his van as he gives you some of his special candies!

You are given ~q~ different sections that you're interested in. For each section, your task is to calculate the final flavour value, including Oree's magical bonus.

Input

The first line contains an integer ~n~ ~(1 \leq n \leq 10^9)~, the number of candies that Oree has in his van.

The second line contains ~n~ space-separated integers ~f_1, f_2, \dots, f_n~ ~(-1000 \leq f_i \leq 1000)~, where ~f_i~ is the flavour value of the ~i~-th candy.

The third line contains an integer ~q~ ~(1 \leq q \leq 10^5)~, the number of sections you want to evaluate.

The next ~q~ lines each contain two integers ~l~ and ~r~ ~(1 \leq l \leq r \leq N)~, representing the start and end indices of a section for each query.

Output

For each query, print the final flavour value of the section ~[l, r]~ after the magical bonus is applied

Example

Input 1

5
-5 3 1 1 12
3
0 2
0 3
0 4

Output 1

-11
100
22

• For the first section you add ~-5~, ~3~ and ~1~ which results in ~-1~. You then also have a ~10~-point deduction so you output ~-1 - 10 = -11~.
• For the second section, you calculate that ~-5 + 3 + 1 + 1 = 0~. You then get the big bonus from Oree and he awards you ~100~ points. So you print out ~100~.
• For the third section, you calculate that ~-5 + 3 + 1 + 1 + 12 = 12~. You then get a ~10~-point award so your total becomes ~22~.