年轻的 Luka 即将进入邪恶女巫 Marica 的房子。他一进屋，女巫就向他提问关于她那含有 $N$ 个数字的数组的问题。Luka 害怕地请求对问题进行解释。Marica 向他解释说，每个询问包含两个整数 $L$ 和 $R$，代表她数组中一个连续子数组的位置。

Luka 的任务是回答每个询问：该连续子数组中，具有“神奇”性质的最长连续子数组（可以是该子数组本身）的长度。如果一个数组的所有值都介于该数组的第一个数和最后一个数的值之间（即包含边界），则称该数组是“神奇”的。例如，$[1, 3, 1, 2, 4]$ 是神奇的，$[4, 1, 1, 2, 1]$ 也是神奇的，而 $[3, 3, 4, 1]$ 不是神奇的。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 500\,000$)，表示数组中数字的个数。

第二行包含 $N$ 个整数 $a_i$ ($1 \le a_i \le 10^9$)。

第三行包含一个整数 $Q$ ($1 \le Q \le 500\,000$)，表示询问的个数。

接下来的 $Q$ 行，每行包含两个整数 $L$ 和 $R$ ($1 \le L \le R \le N$)，代表询问的子数组。

输出格式

输出的第 $i$ 行必须包含一个整数，即对第 $i$ 个询问的答案。

子任务

对于占总分 50% 的测试数据，满足 $N, Q \le 30\,000$。

样例

输入样例 1

5
5 4 3 3 2
3
1 2
1 1
2 4

输出样例 1

2
1
3

输入样例 2

6
6 6 5 1 6 2
3
4 5
4 6
1 4

输出样例 2

2
2
4