该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

给定一个长为 $N$ 的排列 $P$。

有向图 $G$ 由 $N$ 个点和如下边组成：

• 对于 $1<i\le N$，$i$ 向 $i$ 之前第一个满足 $P_j>P_i$ 的 $j$ 连边（没有则不连）。
• 对于 $1\le i< N$，$i$ 向 $i$ 之后第一个满足 $P_j>P_i$ 的 $j$ 连边（没有则不连）。

设 $d(i,j)$ 为 $i$ 到 $j$ 的最短距离（不可达则为 $0$）。

有 $Q$ 次询问，每次询问给出 $l_1,r_1,l_2,r_2$。你需要求出：$\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}d(i,j)$。

Input

第一行输入两个正整数 $N, Q$。

第二行输入 $N$ 个正整数，表示 $P$。

之后 $Q$ 行，每一行输入四个正整数 $l_1, r_1, l_2, r_2$。

Output

输出 $Q$ 行，每行一个整数表示每次询问的答案。

Sample Input 1

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

Sample Output 1

2

3
1
0

Sample Explanation 1

建出来的图有如下有向边：$(1,3), (2,1), (2,3), (4,3), (4,5), (5,3)$。

各点间的距离为：$d(1, 1) = 0, d(1, 2) = 0, d(1, 3) = 1, d(1, 4) = 0, d(1, 5) = 0, d(2, 1) = 1, d(2, 2) = 0, d(2, 3) = 1, d(2, 4) = 0, d(2, 5) = 0, d(3, 1) = 0, d(3, 2) = 0, d(3, 3) = 0, d(3, 4) = 0, d(3, 5) = 0, d(4, 1) = 0, d(4, 2) = 0, d(4, 3) = 1, d(4, 4) = 0, d(4, 5) = 1, d(5, 1) = 0, d(5, 2) = 0, d(5, 3) = 1, d(5, 4) = 0, d(5, 5) = 0$。

Sample Input 2

见 pepper_sample2.in 和 pepper_sample2.out。

满足测试点 $1$ 的数据范围。

Sample Input 3

见 pepper_sample3.in 和 pepper_sample3.out。

满足测试点 $1$ 的数据范围。

Sample Input 4

见 pepper_sample4.in 和 pepper_sample4.out。

满足测试点 $2$ 的数据范围。

Sample Input 5

见 pepper_sample5.in 和 pepper_sample5.out。

满足测试点 $15\sim 21$ 的数据范围。

对于 $100\%$ 的数据，满足 $1\le N, Q\le 5\times 10^5$。

测试点 $1$：$N, Q \le 300$。
测试点 $2$：$N, Q \le 5000$。
测试点 $3$：$N \le 5000$。
测试点 $4, 5$：$N\le 10^5$，且 $P$ 随机生成。
测试点 $6\sim 11$：$l_2 = r_2$。
测试点 $12\sim 14$：$l_1 = r_1$。
测试点 $15\sim 21$：$N, Q\le 10^5$。
测试点 $22\sim 25$：无特殊限制。