描述

SBW来到了XY国
XY国有N个城市，排成一列，每个城市都有XY序列商店
但各个城市XY序列价格不同
SBW有需要从L城走到R城，他想在路上倒卖XY序列赚点小钱钱
SBW买入一条序列需要59.9分钟，卖出一条需要3分钟
但XWQ一直在监视SBW
一但SBW经过已经过的城市或SBW携带了超过一条XY序列或SBW在某城市待了超过1小时
XWQ就会叫ZLY射出三道白光秒杀SBW
为了引诱SBW被杀，XWQ给了SBW一张XY国无限额度信用卡(但到了账单日还是要SBW来还款的……)
SBW不想死，但想知道自己活着最多能赚多少钱

输入

第一行一个整数N
第二行N个整数，为各城市的XY序列价格Ai
第三行一个整数M，为询问个数
接下来M行，一行两个数L,R
表示询问SBW自L至R最大收益

输出

对每个询问输出一行为SBW的收益

样例

输入

4
1 5 2 6
3
1 4
2 4
2 3

输出

8
4
0

范围

30% N<=5 M<=10 |Ai|<=10
50% N<=5000 M<=3000 |Ai|<=1000
80% N<=\(10^5\) M<=50000 |Ai|<=\(10^4+10^4+10^4+10^4+10^4\)
100% N<=\(10^6\) M<=\(10^6-10^5-10^5\) |Ai|<=\(5\ast 10^5\)

限制

2s
128M