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.