Description

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<C \le D$). For each plan, Pak Dengklek wants to know whether the orangutan can start from some tree $s$ ($A \le s \le B$), perform some number of jumps, and reach some tree $e$ ($C \le e \le D$). If the plan is feasible, Pak Dengklek also wants to know the minimum number of jumps needed among all feasible ways.

You need to implement the following functions:

void init(int N, int[] H)

• $N$: the number of trees.
• $H$: an array of size $N$, where $H[i]$ is the height of tree $i$.
• This function will be called exactly once before the first call to minimum_jumps.

int minimum_jumps(int A, int B, int C, int D)

• $A,B$: the range of tree indices that can be used as the starting point.
• $C,D$: the range of tree indices that can be used as the ending point.
• This function should return the minimum number of jumps among all feasible ways, or return $-1$ if the plan is not feasible.
• This function will be called exactly $Q$ times.

Input Format

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.

Output Format

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.

7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2

2
1
-1

Hint

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<j \le N - 1$).
• $0 \le A \le B<C \le D \le N - 1$.

Subtasks

1. (4 points): $H[i]=i+1$ ($0 \le i \le N-1$).
2. (8 points): $N,Q \le 200$.
3. (13 points): $N,Q \le 2000$.
4. (12 points): $Q \le 5$.
5. (23 points): $A=B$, $C=D$.
6. (21 points): $C=D$.
7. (19 points): no additional constraints.

Translated by ChatGPT 5