Bob has a bank account! He uses it every day and it makes him happy.

Since the creation of the account, he has done ~N~ transactions. Each transaction is represented as a decimal dollar amount ~d_i~.

However, Bob is also prone to changing his mind. Sometimes, he regrets buying products that aren't really useful; other times, he accidentally deposits money. Whenever Bob changes his mind, the amount will be listed as ~0~, signifying a reversal of the previous transaction. He can even reverse a reverse and so on.

Bob has ~Q~ queries, asking how much was added or subtracted from his balance from transaction ~L_i~ to transaction ~R_i~ inclusive. He also wants to know his final balance because he can't find it anywhere.

The balance can be negative at any point (Bob can be in debt!).

Input Specification

The first line will contain ~N~ (~1\le N\le 10^6~), the number of transactions in total.

The next ~N~ lines will each either contain a decimal ~d_i~ (~-10^6\le d_i\le10^6~), the amount the balance changed by, or ~0~, a reversal. It is guaranteed that the first transaction will not be ~0~.

The next line will contain ~Q~ (~1\le Q\le10^6~), the number of queries.

The final ~Q~ lines will each contain two integers ~L_i~ and ~R_i~ (~1\le L_i, R_i\le N~), the range of transactions to be considered.

Output Specification

For each query, print the amount of money added or subtracted from his balance between the specified transactions.

Finally, print the total amount of money in the bank account.

Subtasks

Subtask 1 [10%]

• ~1\le N, Q\le 10^3~
• ~-10^3\le d_i\le 10^3~
• There will be no ~0~s in the input.

Subtask 2 [20%]

• ~1\le N, Q\le 10^3~
• ~-10^3\le d_i\le 10^3~

Subtask 3 [70%]

• No further constraints.

Sample Input 1

5
6.50
-3.00
1.99
4.11
-0.12
2
1 3
2 5

Sample Output 1

5.49
2.98
9.48

Sample Input 2

6
12.00
-50.00
0
130.00
-120.00
16.00
4
1 2
2 5
3 3
4 6

Sample Output 2

-38.00
10.00
50.00
26.00
38.00

Explanation for Sample Output 2

For query ~2~, the balance changed by ~-$50.00+$50.00+$130.00-$120.00=$10.00~.

For query ~3~, ~$50.00~ was returned to the balance.