P7599 [APIO2021] 雨林跳跃

本题只支持 C++ 提交，不支持 C++14 (GCC 9)，提交时不需要包含 jumps.h 头文件，只需要将附件中的 jumps.h 中的内容粘贴到代码的开头即可。 由于洛谷的测试点限制，本题只能评测其中的 100 组数据。

在苏门答腊岛的热带雨林中，有 $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

无

无

**【样例解释】** 考虑如下调用： `init(7, [3, 2, 1, 6, 4, 5, 7])` 在初始化完成后，考虑如下调用： `minimum_jumps(4, 4, 6, 6)` 该计划意味着猩猩必须从 $4$ 号树（高度为 $4$）出发，并到达 $6$ 号树（高度为 $7$）。 一种跳跃次数最少的可行方案为：先跳到 $3$ 号树（高度为 $6$），再跳到 $6$ 号树。 另一种方案为：先跳到 $5$ 号树（高度为 $5$），再跳到 $6$ 号树。 因此，`minimum_jumps` 应该返回 $2$。 考虑另一个调用： `minimum_jumps(1, 3, 5, 6)` 该计划意味着猩猩必须从 $1$ 号树（高度为 $2$），$2$ 号树（高度为 $1$），或 $3$ 号树（高度为 $6$）之一出发，并最终到达 $5$ 号树（高度为 $5$）或者 $6$ 号树（高度为 $7$）。 唯一一种跳跃次数最少的可行方案为：从 $3$ 号树出发，直接跳到 $6$ 号树。 因此，`minimum_jumps` 应该返回 $1$。 考虑另一个调用： `minimum jumps(0, 1, 2, 2)` 该计划意味着猩猩必须从 $0$ 号树（高度为 $3$）或者 $1$ 号树（高度为 $2$）出发，并最终到达 $2$ 号树（高度为 $1$）。 由于 $2$ 号树是高度最低的树，所以无法从其他树上跳到 $2$ 号树。 因此，`minimum_jumps` 应该返回 $-1$。 **【数据范围】** - $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