#P15527. [HNOI2026省队集训]胡椒(pepper)

[HNOI2026省队集训]胡椒(pepper)

Statement

给定一个长为 NN 的排列 PP。

有向图 GG 由 NN 个点和如下边组成:

  • 对于 1<i≤N1<i\le N,ii 向 ii 之前第一个满足 Pj>PiP_j>P_i 的 jj 连边(没有则不连)。
  • 对于 1≤i<N1\le i< N,ii 向 ii 之后第一个满足 Pj>PiP_j>P_i 的 jj 连边(没有则不连)。

设 d(i,j)d(i,j) 为 ii 到 jj 的最短距离(不可达则为 00)。

有 QQ 次询问,每次询问给出 l1,r1,l2,r2l_1,r_1,l_2,r_2。你需要求出:∑i=l1r1∑j=l2r2d(i,j)\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}d(i,j)。

Input

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

第二行输入 NN 个正整数,表示 PP。

之后 QQ 行,每一行输入四个正整数 l1,r1,l2,r2l_1, r_1, l_2, r_2。

Output

输出 QQ 行,每行一个整数表示每次询问的答案。

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

[Copy](javascript:;)

Sample Output 1

2

3
1
0

[Copy](javascript:;)

Sample Explanation 1

建出来的图有如下有向边:(1,3),(2,1),(2,3),(4,3),(4,5),(5,3)(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。

满足测试点 11 的数据范围。

Sample Input 3

见 pepper_sample3.in 和 pepper_sample3.out。

满足测试点 11 的数据范围。

Sample Input 4

见 pepper_sample4.in 和 pepper_sample4.out。

满足测试点 22 的数据范围。

Sample Input 5

见 pepper_sample5.in 和 pepper_sample5.out。

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

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

测试点 11:N,Q≤300N, Q \le 300。

测试点 22:N,Q≤5000N, Q \le 5000。

测试点 33:N≤5000N \le 5000。

测试点 4,54, 5:N≤105N\le 10^5,且 PP 随机生成。

测试点 6∼116\sim 11:l2=r2l_2 = r_2。

测试点 12∼1412\sim 14:l1=r1l_1 = r_1。

测试点 15∼2115\sim 21:N,Q≤105N, Q\le 10^5。

测试点 22∼2522\sim 25:无特殊限制。