在苏门答腊岛的热带雨林中，有 \(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 \le D\) ）。若该计划可行，Pak Dengklek 还想知道可行方案中猩猩需要的最少跳跃次数。

已将原题的交互方式转化为传统方式，原题的交互方式使你必须在线的回答每个询问。

第一行两个整数 \(N,Q\) 。

第二行 \(N\) 个整数 \(H[0],H[1],\cdots,H[N-1]\) 。

接下来 \(Q\) 行，每行四个整数 \(A,B,C,D\) 。

输出 \(Q\) 行，每行一个整数答案。

样例解释

第一次询问 4, 4, 6, 6
该计划意味着猩猩必须从 \(4\) 号树（高度为 \(4\) ）出发，并到达 \(6\) 号树（高度为 \(7\) ）。
一种跳跃次数最少的可行方案为：先跳到 \(3\) 号树（高度为 \(6\) ），再跳到 \(6\) 号树。
另一种方案为：先跳到 \(5\) 号树（高度为 \(5\) ），再跳到 \(6\) 号树。
因此答案是 \(2\) 。

第二次询问 1, 3, 5, 6
该计划意味着猩猩必须从 \(1\) 号树（高度为 \(2\) ）， \(2\) 号树（高度为 \(1\) ），或 \(3\) 号树（高度为 \(6\) ）之一出发，并最终到达 \(5\) 号树（高度为 \(5\) ）或者 \(6\) 号树（高度为 \(7\) ）。
唯一一种跳跃次数最少的可行方案为：从 \(3\) 号树出发，直接跳到 \(6\) 号树。
因此答案是 \(1\) 。

第三次询问 0, 1, 2, 2
该计划意味着猩猩必须从 \(0\) 号树（高度为 \(3\) ）或者 \(1\) 号树（高度为 \(2\) ）出发，并最终到达 \(2\) 号树（高度为 \(1\) ）。
由于 \(2\) 号树是高度最低的树，所以无法从其他树上跳到 \(2\) 号树。
因此答案是 \(-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<j \le N - 1\) ）。
• \(0 \le A \le B<C \le D \le N - 1\) 。

子任务

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