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
| Input | Output |
|---|---|
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 |
| Input | Output |
|---|---|
3 1 2 3 6 1 1 2 2 3 3 1 2 2 3 1 3 | 1 2 3 2 4 3 |
