说明

历届世界杯一共有 $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 8

9
5
7
9