CF1824D LuoTianyi and the Function

洛天依给你一个长度为 $n$ 的整数数组 $a$，下标从 $1$ 开始。 定义 $g(i,j)$ 如下： - 当 $i \le j$ 时，$g(i,j)$ 是满足 $\{a_p:i\le p\le j\}\subseteq\{a_q:x\le q\le j\}$ 的最大整数 $x$； - 当 $i>j$ 时，$g(i,j)=0$。 共有 $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$ 次查询的答案。

在第一个样例中： 第一次查询的答案是 $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$。 翻译由 DeepSeek V3 完成