世界杯
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
历届世界杯一共有 $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$
输出格式
对于每一个计划方案，输出一个数字，表示最精彩的比赛有多少进球。样例
8
3 7 9 7 2 5 1 9
4
1 3
6 6
4 6
1 89
5
7
9