Uiro

Aoi has $N$ cards numbered from $1$ to $N$. Each card has a positive integer written on it. The integer written on the card $i$ ($1 ≤ i ≤ N$) is $A\_i$.

Aoi is going to play a game $Q$ times using the cards and a blackboard. The $j$-th game ($1 ≤ j ≤ Q$) she plays consists of the following steps.

1. Write $0$ on the blackboard.

2. Arrange the cards $L\_j , L\_j + 1, \dots , R\_j$ on the desk from left to right in this order.

3. Perform the following operation for $R\_j − L\_j + 1$ times. The $k$-th operation ($1 ≤ k ≤ R\_j − L\_j + 1$) is as follows.

   • Let $x$ be the current integer written on the blackboard, and let $y$ be the integer written on the $k$-th card from the left on the desk. Erase $x$ from the blackboard, and write either $x + y$ or $x − y$ instead. If $x − y$ is chosen, Aoi eats one piece of uiro, a traditional Japanese sweet.
   • However, writing an integer strictly less than $0$ is not allowed.

For each game, you want to know the maximum number of uiro pieces Aoi can eat.

Given the information about cards and games, write a program that, for each game, calculates the maximum number of uiro pieces Aoi can eat.

Read the following data from the standard input.

$N$

$A\_1$ $A\_2$ $\cdots$ $A\_N$

$Q$

$L\_1$ $R\_1$

$L\_2$ $R\_2$

$\vdots$

$L\_Q$ $R\_Q$

Write $Q$ lines to the standard output. In the $j$-th line ($1 ≤ j ≤ Q$), output the maximum number of uiro pieces Aoi can eat in the $j$-th game.

• $1 ≤ N ≤ 200\\, 000$.
• $1 ≤ A\_i ≤ 100$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 200\\, 000$.
• $1 ≤ L\_j ≤ R\_j ≤ N$ ($1 ≤ j ≤ Q$).
• Given values are all integers.