P8037 [COCI 2015/2016 #7] Prokletnik

A magic sequence is defined as a sequence in which the values of all elements are between the first element and the last element (inclusive). Now you are given an array $a$ with $N$ elements. There are $Q$ queries $L, R$. For each query, find the length of the longest magic subarray whose indices in $a$ are within $[L, R]$.

The first line contains an integer $N$. The second line contains $N$ integers $a_i$. The third line contains an integer $Q$. The next $Q$ lines each contain two integers $L, R$.

Output $Q$ lines. Each line contains the answer to one query.

**【Constraints and Notes】** - For $50\%$ of the testdata, $N, Q \le 3 \times 10^4$. - For $100\%$ of the testdata, $1 \le N, Q \le 5 \times 10^5$, $1 \le a_i \le 10^9$, $1 \le L \le R \le N$. **【Hints and Explanation】** **This problem is translated from [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [#7](https://hsin.hr/coci/archive/2015_2016/contest7_tasks.pdf) _Task 6 Prokletnik_.** **The score setting of this problem follows the original COCI problem, with a full score of $160$.** Translated by ChatGPT 5