P7599 [APIO2021] Rainforest Jumping.

This problem only supports C++ submissions and does not support C++14 (GCC 9). When submitting, you do not need to include the `jumps.h` header file; you only need to paste the content of `jumps.h` from the attachment at the beginning of your code.

In the tropical rainforest on Sumatra Island, there are $N$ trees in a row. From left to right, they are numbered from $0$ to $N-1$. The height of tree $i$ is $H[i]$, and all tree heights are **pairwise distinct**. Pak Dengklek is training an orangutan so that she can jump from one tree to another. In one jump, the orangutan can jump left or right from the current tree to the first tree that is taller than the current one. Formally, if the orangutan is currently on tree $x$, then she can jump to tree $y$ if and only if one of the following holds: - $y$ is the largest non-negative integer less than $x$ among all $z$ such that $H[z]>H[x]$; or: - $y$ is the smallest non-negative integer greater than $x$ among all $z$ such that $H[z]>H[x]$. Pak Dengklek has $Q$ jumping plans. Each plan is described by four integers $A$, $B$, $C$, and $D$ ($A \le B

The sample grader program reads the input in the following format: - Line $1$: $N$ $Q$. - Line $2$: $H[0]$ $H[1]$ $\cdots$ $H[N-1]$. - Line $3+i$ ($0 \le i \le Q-1$): $A$ $B$ $C$ $D$, representing the parameters of the $i$-th call to `minimum_jumps`.

The sample grader program outputs your answers in the following format: - Line $1+i$ ($0 \le i \le Q-1$): the return value of the $i$-th call to `minimum_jumps`.

**Sample Explanation** Consider the following call: `init(7, [3, 2, 1, 6, 4, 5, 7])` After initialization, consider the following call: `minimum_jumps(4, 4, 6, 6)` This plan means the orangutan must start from tree $4$ (height $4$) and reach tree $6$ (height $7$). One feasible way with the minimum number of jumps is: first jump to tree $3$ (height $6$), then jump to tree $6$. Another way is: first jump to tree $5$ (height $5$), then jump to tree $6$. Therefore, `minimum_jumps` should return $2$. Consider another call: `minimum_jumps(1, 3, 5, 6)` This plan means the orangutan must start from one of tree $1$ (height $2$), tree $2$ (height $1$), or tree $3$ (height $6$), and finally reach either tree $5$ (height $5$) or tree $6$ (height $7$). The only feasible way with the minimum number of jumps is: start from tree $3$ and jump directly to tree $6$. Therefore, `minimum_jumps` should return $1$. Consider another call: `minimum jumps(0, 1, 2, 2)` This plan means the orangutan must start from either tree $0$ (height $3$) or tree $1$ (height $2$), and finally reach tree $2$ (height $1$). Since tree $2$ has the smallest height, it is impossible to jump to tree $2$ from any other tree. Therefore, `minimum_jumps` should return $-1$. **Constraints** - $2 \le N \le 2 \times {10}^5$. - $1 \le Q \le {10}^5$. - $1 \le H[i] \le N$ ($0 \le i \le N - 1$). - $H[i]\ne H[j]$ ($0 \le i