Magical Subarrays

Luka walks into the house of the witch Marica, and she starts questioning him about her array $A$ of $N$ numbers. Each question is a pair of integers $L$ and $R$ that marks the subarray running from $A_L$ to $A_R$.

For every question Luka has to answer with the length of the longest magical subarray contained in that subarray. The whole queried subarray is allowed.

A subarray is magical when every value in it lies between its first value and its last value. That is, $A_l, A_{l+1}, \dots, A_r$ is magical when $\min(A_l, A_r) \le A_k \le \max(A_l, A_r)$ holds for every $k$ with $l \le k \le r$.

For example, $[1, 3, 1, 2, 4]$ and $[4, 1, 1, 2, 1]$ are magical, while $[3, 3, 4, 1]$ is not. A subarray of length 1 is always magical, so every answer is at least 1.

The first line contains the length of the array $N$. ($1 \le N \le 500\,000$)

The second line contains the elements $A_1, A_2, \dots, A_N$, separated by spaces. ($1 \le A_i \le 10^9$)

The third line contains the number of questions $Q$. ($1 \le Q \le 500\,000$)

Each of the next $Q$ lines contains two integers $L$ and $R$, in that order. ($1 \le L \le R \le N$)

Print the answer to the $i$th question on the $i$th line, as a single integer.