题目背景

风见幽香是一个文雅的女孩子，平日里最大的爱好就是种花。

题目描述

这天，她来到太阳花田，打算为她的花浇水。看着花圃中参差不齐的太阳花，她突发奇想，打算对它们做一些试验。

风见幽香的太阳花圃可以看做一条直线，上面栽种有 $n$ 株太阳花，太阳花在这条直线上按高度从小到大排列，形成高度序列 $a$，其中第 $i$ 株太阳花的高度为 $a_{i}$。

接下来，风见幽香想做 $m$ 次试验，每次试验会选定一个区间 $\left [ l,r \right ]$ ，将其中的太阳花依次转移到另一块赋予魔法的花田。记该次试验一共转移了 $k$ 株太阳花，则转移后太阳花高度 $b_{1},b_{2},...,b_{k}$ 与 $a_{l},a_{l+1},...,a_{r}$ 一致。通俗地讲，转移后太阳花的顺序不会改变。

然后，从第 $1$ 天开始，魔法花田中的魔力便会生效。具体的讲，在第 $t$ 天时 $(t>0)$，对于转移后的第 $i$ 株太阳花 $(1\le i < k)$，如果第 $t-1$ 天满足 $b_{i}<b_{i+1}$，那么这株太阳花便会生长一个高度，即高度由 $b_{i}$ 变为 $b_{i}+1$。特别地，第 $k$ 株太阳花永远不会生长。

可以证明最终所有太阳花的高度都会到达 $b_{k}$ ，而风见幽香想知道，对于每组试验，最早在第几天时，魔法花田中的所有太阳花高度均到达 $b_{k}$。

由于风见幽香爱花如子，试验结束后她会将太阳花恢复原来的高度并重新转移到原来的太阳花圃。形式化地讲，试验间相互独立，即试验并不会改变原序列 $a$ 的值。

风见幽香请求你帮帮她。

输入格式

第一行一个正整数 $n$，表示高度序列 $a$ 的长度

第二行 $n$ 个正整数，表示高度序列 $a$。

第三行一个正整数 $m$，表示试验数量。

接下来 $m$ 行，每行两个正整数 $l_{i},r_{i}$ ，表示每次试验的区间。

输出格式

共 $m$ 行，每行一个整数，表示使得魔法花田中全部太阳花高度均变为 $b_{k}$ 的最小天数 $t$。

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

6
2
5
0

提示

【询问3解释】

下方展示了太阳花每天的高度变化。

3 3 7 -> 3 4 7 -> 4 5 7 -> 5 6 7 -> 6 7 7 -> 7 7 7

【样例 #2】

见附件目录下的 flower/flower2.in 与 flower/flower2.ans。

这个样例满足测试点 $2\sim3$ 的条件限制。

【样例 #3】

见附件目录下的 flower/flower3.in 与 flower/flower3.ans。

这个样例满足测试点 $10\sim12$ 的条件限制。

【样例 #4】

见附件目录下的 flower/flower4.in 与 flower/flower4.ans。

这个样例满足测试点 $19\sim20$ 的条件限制。

【数据范围】

对于全部数据，保证 $1\le n,m \le 2\times10^5$，$1\le l_{i} \le r_{i}\le n$，$1\le a_{i}\le 10^9$。

• 特殊性质A ：所有 $a_{i}$ 均相等。
• 特殊性质B ：对于所有试验满足 $r_{i}=n$。
• 特殊性质C ：对于 $1\le {i} < n$，$a_{i}+1=a_{i+1}$
• 特殊性质D ：保证 $a$ 由 $n$ 个在 $\left [1,10^9\right]$的范围内随机选取的正整数排序得到。