Gotham city is in danger. All the people from Gotham were airlifted and they are going to be dropped at different districts of a new safe city.

There are $N$ districts located at position $(1, 2, \ldots, N)$ in a straight line in this newly built safe city.
An array(P) is given which tells us about the maximum capacity of people that can be accommodated in the districts.

There is a condition that people can move only in the forward direction(i.e from city $i$ to $i+1$ for $1 ≤ i < N$) to get shelter.
People want to travel as little as possible to get shelter.
The sad part is that in case any person who does not get shelter is going to die.

Initially, all the districts in the new city are empty.

You are asked $Q$ queries.
Each query consists of two Integers $X$ and $K$, where $K$ denotes the number of people who are going to be dropped at district $X$.
You are required to print the total sum of distance traveled by the people in the current query(that got shelter or did not die) in a new line.

Note:- Queries are not independent(they depend on the previous queries).

------ Input ------

First Line consists of one Integer $N$, where $N$ is the number of districts.
Second line consists of $N$ integers of (array P) separated by a space.
Third Line contains an integer $Q$, which denotes the number of queries.
Next, $Q$ lines consist of two integers $X$ and $K$ separated by space.

------ Output ------

For each query, you have to print the total sum of distance traveled by the people in the current query(that got shelter or did not die ) in a new line.

------ Constraints ------

$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$1 ≤ X ≤ N$
$1 ≤ P[i] ≤ 10^{9}$
$1 ≤ K ≤ 10^{9}$

------ Example Input ------

4
5 5 6 1
2
2 11
2 3

------ Example Output ------

6
2

------ Explanation ------

Query $1$: $5$ people will get shelter in city $2$ and the remaining $6$ will get shelter in city $3$. So, the total distance covered in this query is $6$.
Query $2$: Only $1$ person can get shelter in city $4$ and the rest will die. So, the total distance traveled is $2$.

见题面

见题面