Monkey Jungle Jump

In a tropical rainforest on Sumatra, there are (N) trees arranged in a line and numbered from (0) to (N-1). The height of tree (i) is given by (H[i]) and all heights are distinct. A monkey is trained to jump from tree to tree. During a single jump, if the monkey is at tree (x), it can jump to tree (y) if and only if one of the following conditions holds:

1. (y) is the largest index smaller than (x) such that (H[y] > H[x]) (i.e. the first tree to the left that is taller than tree (x)).
2. (y) is the smallest index greater than (x) such that (H[y] > H[x]) (i.e. the first tree to the right that is taller than tree (x)).

You are given (Q) jump plans. Each plan is described by four integers (A, B, C, D) (with (A \le B < C \le D)). For each plan, determine whether it is possible for the monkey to start from some tree (s) with (A \le s \le B) and, after a number of jumps, reach some tree (e) with (C \le e \le D). If it is possible, find the minimum number of jumps required; otherwise, return (-1).

You need to implement the following two functions:

(void init(int N, int[] H))

• (N): the number of trees.
• (H): an array of size (N) where (H[i]) represents the height of tree (i).
• This function is called exactly once before any call to (minimum_jumps).

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

• (A, B): the range of valid starting tree indices.
• (C, D): the range of valid ending tree indices.
• The function should return the minimum number of jumps required for a valid sequence, or (-1) if no such sequence exists.

Note: Since every jump moves the monkey to a strictly taller tree, the sequence of jumps is acyclic.

inputFormat

The input begins with two integers (N) and (Q) on the first line, representing the number of trees and the number of queries, respectively. The second line contains (N) integers (H[0], H[1], \dots, H[N-1]) representing the heights of the trees. Each of the following (Q) lines contains four integers (A), (B), (C), and (D) (with (A \le B < C \le D)), describing a jump plan.

outputFormat

For each query, output the minimum number of jumps required for the monkey to travel from a starting tree in the range ([A, B]) to a destination tree in the range ([C, D]). If it is not possible, output (-1). Each answer should be printed on a new line.

sample

5 3
2 3 1 5 4
0 1 2 3
0 1 3 4
2 2 4 4

1
1
-1