题目描述

小男孩 Zakhar 在经历信息学奥赛失意后，决定养兔子。他买了 $n$ 只兔子，并按体重非降序给它们编号。初始时，第 $i$ 只兔子的体重为 $w_i$ 千克。

Zakhar 发现，如果把一段兔子按体重非降序排成一排，那么每天每只满足“它的体重小于后一只兔子体重”的兔子，体重都会增加 $1$ 千克。更形式化地说，每天第 $i$ 只兔子会增加 $1$ 千克，当且仅当它不是队伍最后一只，并且 $w_i \ne w_{i+1}$。所有变化同时发生。

这个过程持续到队伍中所有兔子的体重都等于最后一只兔子的体重为止。

Zakhar 想回答 $m$ 个询问：如果只取编号从 $l_i$ 到 $r_i$ 的兔子排成一排，需要多少天后这些兔子的体重不再变化？

输入格式

第一行包含一个整数 $n$，表示兔子数量。

第二行包含 $n$ 个整数 $w_1,w_2,\dots,w_n$，表示兔子体重。保证该序列非降序，即 $w_i \le w_{i+1}$。

第三行包含一个整数 $m$，表示询问数量。

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$，表示一个询问区间。

输出格式

对于每个询问，输出一行一个整数，表示体重停止变化所需的天数。可以证明这个时间一定存在。

数据范围

$1 \le n \le 200000$，$1 \le w_i \le 10^9$，$1 \le m \le 200000$，$1 \le l_i \le r_i \le n$。

样例

4
1 3 3 7
4
1 4
1 3
2 4
2 3

6
2
5
0

样例解释

对于询问 $[1,4]$，最开始体重为 $[1,3,3,7]$：

• 若某只兔子比后一只轻，它当天增加 $1$；
• 所有兔子的增长同时发生；
• 经过若干天后，区间内所有兔子都会达到最后一只兔子的体重。

该询问的答案为 $6$；其余询问答案如样例所示。

子任务