题面描述

在苏门答腊岛的热带雨林中，有 $N$ 棵树排成一排，从左到右依次用 $0$ 到 $N - 1$ 进行编号，其中 $i$ 号树的高度为 $H[i]$，且所有树的高度互不相同。 Pak Dengklek 正在训练一只猩猩，让她能够从一棵树上跳到另一棵树上。对于一次跳跃，猩猩可以从一棵树向左或向右跳到比当前这棵树高的第一棵树上。形式化地，如果猩猩当前在 $x$ 号树，那么当且仅当满足下列条件之一时，她能够跳到 $y$ 号树上:

• $y$ 是满足 $H[z] > H[x]$ 的所有 $z$ 中比 $x$ 小的最大非负整数；
• $y$ 是满足 $H[z] > H[x]$ 的所有 $z$ 中比 $x$ 大的最小非负整数。

Pak Dengklek 有 $Q$ 个跳跃计划，每个计划用四个整数 $A,B,C$ 和 $D~(A\le B<C\le D)$ 来描述。对于每个计划，Pak Dengklek 想知道猩猩是否能够从某棵树 $s~(A \le s \le B)$ 出发，经过若干次跳跃，到达某棵树 $e~(C \le e\leq D)$。若该计划可行，Pak Dengklek 还想知道可行方案中猩猩需要的最少跳跃次数。

实现细节

你需要在程序开始引入 jumps.h 头文件。

你需要实现下列函数：

void init(int N, int[] H)

• N：树的数量。
• H：大小为 $N$ 的数组，$H[i]$ 表示 $i$ 号树的高度。
• 该函数在第一次 minimum_jumps 的调用前，将会被调用恰好一次。

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

• $A,~B$：可以用作起点的树的编号范围。
• $C,~D$：可以用作终点的树的编号范围。
• 该函数需要返回可行方案中猩猩需要的最少跳跃次数，或者返回 -1 表示该计划不可行。
• 该函数将被调用恰好 $Q$ 次。

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

2
1
-1

约束

• $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$

子任务

1. (4 分) $H[i] = i + 1$ (for all $0 \le i \le N - 1$)
2. (8 分) $N \le 200$, $Q \le 200$
3. (13 分) $N \le 2000$, $Q \le 2000$
4. (12 分) $Q \le 5$
5. (23 分) $A = B$, $C = D$
6. (21 分) $C = D$
7. (19 分) 无附加限制

示例测试程序

示例测试程序按如下格式读取输入数据：

• 第 $1$ 行: $N \; Q$
• 第 $2$ 行: $H[0] \; H[1] \; \ldots \; H[N - 1]$
• 第 $3 + i$ ($0 \le i \le Q - 1$) 行: $A \; B \; C \; D$，表示第 $i$ 次 minimum_jumps 调用的参数。

示例测试程序按如下格式输出你的答案：

• 第 $1 + i$ ($0 \le i \le Q - 1$) 行: 第 $i$ 次 minimum_jumps 调用的返回值。