P8037 [COCI 2015/2016 #7] Prokletnik

定义魔法序列为满足所有元素的大小均在第一个元素和最后一个元素之间的序列。 现有一个元素个数为 $N$ 的数组 $a$。给出 $Q$ 次询问 $L,R$，求 $a$ 中下标在 $[L,R]$ 之间的最长的子魔法区间。

无

无

**【数据规模与约定】** - 对于 $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](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 6 Prokletnik_。** **本题分值按 COCI 原题设置，满分 $160$。**