题目描述

Bobi 住进了一片森林。森林中有 $N$ 棵树排成一条直线，编号为 $0$ 到 $N-1$。第 $i$ 棵树的高度为 $H_i$，这些高度互不相同，并且构成 $1,2,\ldots,N$ 的一个排列。

Bobi 站在树 $x$ 上时，可以跳到某棵树 $y$，当且仅当满足下列条件之一：

• $y<x$，$H_y>H_x$，并且对所有 $y<i<x$，都有 $H_i<H_x$；
• $y>x$，$H_y>H_x$，并且对所有 $x<i<y$，都有 $H_i<H_x$。

也就是说，他只能跳到左右两侧第一个“能越过中间所有树”的更高树。

现在有 $Q$ 个询问。每个询问给出四个整数 $A,B,C,D$，满足

Bobi 可以从编号在 $[A,B]$ 中的任意一棵树开始，最终要到达编号在 $[C,D]$ 中的任意一棵树。求最少需要多少次跳跃；若无法到达，返回 $-1$。

实现方式

本题为函数式提交题，需要实现两个函数：

void init(int N, std::vector<int> H);
int minimum_jumps(int A, int B, int C, int D);

• init 会被调用一次，给出 $N$ 和高度数组 $H$；
• minimum_jumps 会被调用 $Q$ 次，每次返回对应询问的答案。

数据范围

• $2\le N\le 200000$；
• $1\le Q\le 100000$；
• $1\le H_i\le N$；
• $H_i$ 两两不同；
• $0\le A\le B<C\le D\le N-1$。

子任务

本地测试格式

本地 grader 的输入格式：

• 第一行：$N,Q$；
• 第二行：$H_0,H_1,\ldots,H_{N-1}$；
• 接下来 $Q$ 行：$A,B,C,D$。

样例

输入

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

输出

2
1
-1

样例解释

三次询问对应的最优跳跃路径分别为：

1. $4\to 3\to 6$；
2. $3\to 6$；
3. 不存在可行路径。

@下发文件