Recently, cryptocurrencies have become increasingly popular. Ann decided that it was about time she started mining the Dogecoin cryptocurrency. Ann's computer is not very powerful, so Ann mines exactly $1$ Dogecoin per day. On the Internet, there are forecasts of the cost of $1$ dogecoin for the next $n$ days. Every day, Ann can sell any amount of dogecoin that she currently has. Note that if Ann mined Dogecoin on the $i$-th day, then she can sell it on the same day.

Ann has not yet decided when to start mining. She has prepared $q$ possible plans and for each of them wants to know the maximum profit that she can get. Each of the plans is described by two numbers $l$ and $r$ — the first and last days of mining. Note that Ann should not have any Dogecoin left after the $r$-th day.

Input

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), where $c_i$ is the cost of Dogecoin on the $i$-th day.

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of Ann's plans.

The following $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the first and last days of mining.

Output

For each Ann's plan print one integer — the maximum profit that she can get using this plan.

见题面 Input 部分

见题面 Output 部分