1710: 世界杯
Time Limit: 1 Sec
Memory Limit: 256 MB
Submission：0
AC：0
Score：100.00
历届世界杯一共有 $n$ 场比赛，每一场比赛都有一个比分。
最近小明沉迷于世界杯，并且决定观看连续一段时间的世界杯比赛。他会观看其中每一场比赛。
他认为，一场比赛中，进球越多，比赛就越精彩。
现在他提出了 $m$ 个方案，每一个方案是一段时间区间，他想预测一下他能看到的最精彩的比赛有多少个进球呢？
第一行一个正整数 $n$，表示一共有 $n$ 场比赛。
接下来一行一共有 $n$ 个非负整数，由空格分隔，表示每一场比赛双方进球总数。
第三行有一个正整数 $m$，表示一共有 $m$ 个计划方案。
之后 $m$ 行，每一行两个数，$L$ 和 $R$，表示在这个计划当中他打算看从第 $L$ 场到第 $R$ 场之内的所有比赛。
$1\leq N\leq 10^5$
$0\leq M\leq 10^5$
每一个比赛的进球数 $\leq 10^5$
$1\leq L\leq R\leq n$
对于每一个计划方案，输出一个数字，表示最精彩的比赛有多少进球。
input:
8
3 7 9 7 2 5 1 9
4
1 3
6 6
4 6
1 8
output:
9
5
7
9