Problem Description

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]$.

Input Format

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 Format

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

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

Hint

【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 #7 Task 6 Prokletnik.

The score setting of this problem follows the original COCI problem, with a full score of $160$.

Translated by ChatGPT 5