write a go solution for Description:
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 Format:
The first line contains one integer n (1<=n<=2*10^5).

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

The third line contains one integer q (1<=q<=2*10^5) — the number of Ann's plans.

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

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

Note:
None. Output only the code with no comments, explanation, or additional text.