题目描述

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

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

输入格式

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

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

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

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

输出格式

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

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

2
1
3

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

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$。

【提示与说明】

题目译自 COCI 2015-2016 #7 Task 6 Prokletnik。

本题分值按 COCI 原题设置，满分 $160$。