Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Donate Our Department

By aLmAHFUz · Limits 1s, 512 MB

We are students of CSE, IU. It is very well known that our departmental instruments are not so good. So we, students, want to donate our department. But some are not interested to donate. For collecting the donation we have arranged the student in a long line according to their roll numbers in ascending order. We may not receive donation from all students, so we will receive from the students of roll a to b (example, 4 to 7). Now your task is to find the total amount of donation.

Every student have at least (some) positive amount but the student who are not interested to donate will be denoted with -1, also -1 will divide the long line into more groups . For example, 1 2 -1 4 -1 5 6. Here the two -1 divide the line into 3 groups. We will receive same amount from every member of a group, the amount will be the minimum amount among them. See the example carefully.

Say, we have students with these amount -1 3 4 2 -1 -1 4 7 3 4. If we want to receive from roll 1 to 8, the total amount will be (0+2+2+2+0+0+4+4) = 14. If we receive from roll 1 to 10 (all), the total amount will be (0+2+2+2+0+0+3+3+3+3) = 18.

Input

Input will start with an integer n. Second line contain n integers (a1, a2, a3.............an). Third line contain an integer q. Then q lines (or line) contain a, b. Every (input) integer is less or equal than 10^5.

Output

For each query , you have to print a single line having the expected answer.

Samples

InputOutput
10
-1 3 4 2 -1 -1 4 7 3 4
5
1 10
1 3
2 3
3 3
3 8

18
6
6
4
12

InputOutput
3
1 2 3
6
1 1
2 2
3 3
1 2
2 3
1 3

1
2
3
2
4
3


Statistics

29% Solution Ratio

subhashis_cseEarliest, Mar '20

subhashis_cseFastest, 0.1s

Alomgir27Lightest, 6.6 MB

subhashis_cseShortest, 2277B