마법의 구간

루카가 마녀 마리차의 집에 들어서자, 마리차는 자기가 가진 $N$개의 수로 이루어진 배열 $A$를 두고 질문을 던지기 시작한다. 질문 하나는 두 정수 $L$과 $R$로 이루어지고, 배열에서 $A_L$부터 $A_R$까지 이어지는 구간을 가리킨다.

루카는 질문마다 그 구간 안에 들어 있는 연속한 구간 중 마법 구간인 것의 최대 길이를 답해야 한다. 구간 전체를 골라도 된다.

구간에 들어 있는 모든 값이 첫 번째 값과 마지막 값 사이에 있으면 그 구간은 마법 구간이다. 즉 $A_l, A_{l+1}, \dots, A_r$가 마법 구간이라는 것은 $l \le k \le r$인 모든 $k$에 대해 $\min(A_l, A_r) \le A_k \le \max(A_l, A_r)$가 성립한다는 뜻이다.

예를 들어 $[1, 3, 1, 2, 4]$와 $[4, 1, 1, 2, 1]$은 마법 구간이지만 $[3, 3, 4, 1]$은 마법 구간이 아니다. 길이가 1인 구간은 언제나 마법 구간이므로 답은 항상 1 이상이다.

첫째 줄에 배열의 길이 $N$이 주어진다. ($1 \le N \le 500\,000$)

둘째 줄에 배열의 원소 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 10^9$)

셋째 줄에 질문의 개수 $Q$가 주어진다. ($1 \le Q \le 500\,000$)

이어지는 $Q$개의 줄에 질문의 두 정수 $L$과 $R$가 순서대로 주어진다. ($1 \le L \le R \le N$)

$i$번째 줄에 $i$번째 질문의 답을 정수 하나로 출력한다.