밀림 점프

수마트라의 열대 밀림에, 왼쪽부터 오른쪽으로 0부터 $N - 1$ 까지 번호가 매겨진 $N$ 그루의 나무가 있다. 각각의 나무의 높이는 모두 다르다. 나무 $i$ 의 높이는 $H\[i]$ 이다.

이 교수는 오랑우탄을 훈련시켜서 나무 사이를 점프해서 다니게 하고 있다. 한번 점프할 때, 오랑우탄은 현재 있는 나무의 꼭대기에서, 왼쪽 또는 오른쪽으로 현재 나무 높이보다 더 높은 가장 가까운 나무로 점프할 수 있다. 엄밀하게는, 현재 오랑우탄이 나무 $x$ 에 있다면 점프해서 이동하게 되는 나무가 $y$ 라는 것은 다음 두 조건 중 하나를 만족한다는 것과 동치이다.

$y$ 는 $H\[y] > H\[x]$ 이자 $x$ 보다 작은 가장 큰 음이 아닌 정수이다. 또는
$y$ 는 $H\[y] > H\[x]$ 이자 $x$ 보다 큰 가장 작은 음이 아닌 정수이다.

이 교수는 오랑우탄을 점프시킬 $Q$ 가지의 계획을 가지고 있다. 각 계획은 네 정수 $A$ , $B$ , $C$ , $D$ ( $A \le B < C \le D$ )로 표현된다. 이 교수는 오랑우탄이 어떤 나무 $s$ ( $A \le s \le B$ )에서 시작해서 점프를 통해서 최종적으로 나무 $e$ ( $C \le e \le D$ )에 도착할 수 있는 지 알고 싶다. 만약 가능하다면, 오랑우탄이 최소 횟수 점프를 해서 이 계획을 달성하게 하고 싶다.

문제

제한