题目描述

定义魔法序列为满足所有元素的大小均在第一个元素和最后一个元素之间的序列。

现有一个元素个数为 $N$ 的数组 $a$。给出 $Q$ 次询问 $L,R$，求 $a$ 中下标在 $[L,R]$ 之间的最长的子魔法序列。

输入格式

第一行，一个整数 $N$。

第二行，$N$ 个整数 $a_i$。

第三行，一个整数 $Q$。

接下来的 $Q$ 行，每行两个整数 $L,R$。

输出格式

输出 $Q$ 行，每行对应一次询问的答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
1
3

样例 #2

样例输入 #2

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

样例输出 #2

2
2
4

提示

【数据规模与约定】

• 对于 $50\%$ 的数据，$N,Q \le 3 \times 10^4$。
• 对于 $100\%$ 的数据，$1 \le N,Q \le 5 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le L \le R \le N$。