Rainforest Jump

In a tropical rainforest in Sumatra, there are $N$ trees numbered from 0 to $N - 1$ from left to right. All trees have different heights. The height of tree $i$ is $H[i]$.

A professor is training orangutans to move by jumping between trees. In one jump, an orangutan at the top of its current tree can jump left or right to the nearest tree that is taller than the current tree. Precisely, an orangutan at tree $x$ can jump to tree $y$ if and only if one of the following holds:

• $H[y] > H[x]$, and $y$ is the largest nonnegative integer less than $x$ with this property.
• $H[y] > H[x]$, and $y$ is the smallest nonnegative integer greater than $x$ with this property.

The professor has $Q$ plans for the orangutans. Each plan is given by four integers $A$, $B$, $C$, $D$ ($A \le B < C \le D$). The professor wants to know whether an orangutan can start at some tree $s$ ($A \le s \le B$) and, through jumps, finally reach some tree $e$ ($C \le e \le D$). If it is possible, the professor wants the orangutan to complete the plan with the fewest possible jumps.

• $2 \le N \le 200\,000$
• $1 \le Q \le 100\,000$
• $1 \le H[i] \le N$ (for all $0 \le i \le N - 1$)
• $H[i] \neq H[j]$ (for all $0 \le i < j \le N - 1$)
• $0 \le A \le B < C \le D \le N - 1$