밀림 점프

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

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

• $H[y] > H[x]$이고, $y$는 $x$보다 작은 0 이상의 정수 중 이 조건을 만족하는 가장 큰 값이다.
• $H[y] > H[x]$이고, $y$는 $x$보다 큰 0 이상의 정수 중 이 조건을 만족하는 가장 작은 값이다.

교수는 오랑우탄을 위한 계획을 $Q$개 가지고 있다. 각 계획은 정수 네 개 $A$, $B$, $C$, $D$($A \le B < C \le D$)로 주어진다. 교수는 오랑우탄이 어떤 나무 $s$($A \le s \le B$)에서 출발해 점프를 거듭하여 최종적으로 나무 $e$($C \le e \le D$)에 도착할 수 있는지 알고 싶다. 가능하다면, 교수는 오랑우탄이 가능한 한 가장 적은 횟수로 점프해서 계획을 완수하기를 원한다.

• $2 \le N \le 200\,000$
• $1 \le Q \le 100\,000$
• $1 \le H[i] \le N$ (모든 $0 \le i \le N - 1$에 대해)
• $H[i] \neq H[j]$ (모든 $0 \le i < j \le N - 1$에 대해)
• $0 \le A \le B < C \le D \le N - 1$