LuoTianyi 给你一个 $$$a$$$ 的数组 $$$n$$$ 个整数,索引从 $$$1$$$ 开始。
定义 $$$g(i,j)$$$ 如下:
- $$$g(i,j)$$$ 是满足 $$$\{a_p:i\le p\le j\}\subseteq\{a_q:x\le q\le j\}$$$ 而 $$$i \le j$$$ 的最大整数 $$$x$$$;
- 且$$$g(i,j)=0$$$,而$$$i>j$$$。
有 $$$q$$$ 查询。对于每个查询,您都会获得四个整数$$$l,r,x,y$$$,您需要计算$$$\sum\limits_{i=l}^{r}\sum\limits_{j=x}^{y}g(i,j)$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\le n,q\le 10^6$$$) — 数组 $$$a$$$ 的长度和查询次数。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — 数组 $$$a$$$ 的元素。
接下来的 $$$q$$$ 行描述一个查询。第 $$$i$$$ 行包含四个整数 $$$l,r,x,y$$$ ($$$1\le l\le r\le n, 1\le x\le y\le n$$$) — 第 $$$i$$$ 查询中的整数。
输出
打印 $$$q$$$ 行,其中第 $$$i$$$ 行包含一个整数 — 第 $$$i$$$ 查询的答案。
示例
输入 #1
6 4 1 2 2 1 3 4 1 1 4 5 2 3 3 3 3 6 1 2 6 6 6 6
输出 #1
6 6 0 6
输入 #2
10 5 10 2 8 10 9 8 2 1 1 8 1 1 10 10 2 2 3 3 6 6 6 6 1 1 4 5 4 8 4 8
输出 #2
4 2 6 4 80
注意
在第一个示例中:
在第一个查询中,答案是 $$$g(1,4)+g(1,5)=3+3=6$$$。
$$$x=1,2,3$$$ 可以满足 $$$\{a_p:1\le p\le 4\}\subseteq\{a_q:x\le q\le 4\}$$$,$$$3$$$ 是最大整数,所以 $$$g(1,4)=3$$$。
在第二个查询中,答案是 $$$g(2,3)+g(3,3)=3+3=6$$$。
在第三个查询中,答案是 $$$0$$$,因为所有 $$$i > j$$$ 且 $$$g(i,j)=0$$$。
在第四个查询中,答案是$$$g(6,6)=6$$$。
在第二个示例中:
在第二个查询中,答案是 $$$g(2,3)=2$$$。
在第四个查询中,答案是$$$g(1,4)+g(1,5)=2+2=4$$$。