题目描述

你是一位著名的魔法师，你正在研究一种叫做"魔法序列"的神秘力量。

在你的世界里，魔法序列被定义为满足所有元素的魔力值均在第一个元素和最后一个元素的魔力值之间的序列。

你手中有一本古老的魔法书，书中记录了 $N$ 个魔法符文，每个符文都有一个特定的魔力值，组成了一个数组 $a$。书中的符文并不是随机排列的，而是按照某种神秘的规律排列，你需要解开这个谜团。

在你的研究过程中，你会进行 $Q$ 次实验。在每次实验中，你会选择一段连续的符文，下标在 $[L,R]$ 之间，然后尝试找出这段符文中最长的子魔法序列。

你的任务是，通过对魔法书的研究，找出每次实验中最长的子魔法序列，以解开魔法书中隐藏的秘密。

输入格式

第一行一个整数 $N$ 表示序列的长度。

接下来第二行 N 个整数表示序列 $a_i$。

第三行一个整数 $Q$ 表示实验次数。

接下来 $Q$ 行，每行两个整数 $L, R$ 表示实验区间。

输出格式

$Q$ 行整数表示答案。

10
4 5 13 15 1 2 12 12 7 13
5
1 6
3 5
4 9
5 7
2 5

4
2
4
3
3

10
1 7 7 3 11 4 4 14 4 13
5
1 4
1 8
3 8
2 5
2 4

3
8
5
3
3

提示

对于 $20\%$ 的数据满足 $n,q \le 500$。

对于 $50\%$ 的数据满足 $n,q \le 10000$。

对于 $70\%$ 的数据满足 $n,q \le 100000$。

对于 $100\%$ 的数据满足 $n,q \le 500000$。$0 \le a_i \le 10^9, 1\le L_i,R_i \le n$