题目描述

Yuto和Platina准备玩一个不降子数组游戏.

具体的, 给定一个长度为$N$的数组$A$, 和区间限制$L$和$R$.

Yuto首先在$[L, R]$中选择一个数字, 并展示给Platina看.

随后Platina也会选择一个在$[L, R]$中的数字.

我们不妨设Yuto选择了数字$a$, Platina选择了数字$b$.

这局游戏的得分是$A[min(a,b):max(a,b)]$的不降子数组的个数. ($A[l:r]$表示由数组$A$下标从$l$到$r$这一连续段构成的新数组).

注 : 数组$B$的子数组是从$B$的头尾连续删除若干(可以为空)个元素后得到的新数组.

Yuto想要得分尽可能的小, Platina想要得分尽可能的大.

他们将会在一个数组上游戏$Q$次, 对于每次游戏, 请输出最后游戏的得分.

输入格式

第一行输入一个正整数$N$, 表示数组$A$的长度.

接下来一行$N$个正整数, 分别表示$A_1$, $A_2$, ... , $A_N$.

第三行输入一个正整数$Q$, 表示游戏进行的次数.

接下来$Q$行, 每一行输入两个正整数, 分别表示$L$和$R$.

对于所有数据, 满足$1 \leq N, Q \leq 5 \times 10^5$, $1 \leq A_i \leq 10^9$ 且 $1 \leq L \leq R \leq N$.

输出格式

对于每次游戏, 输出一个正整数, 表示游戏最后的得分.

样例输入

8
7 10 3 1 9 5 5 2 
5
1 5
2 2
5 8
1 8
3 5

样例输出

4
1
4
7
3