CF1824D.LuoTianyi and the Function

LuoTianyi gives you an array $a$ of $n$ integers and the index begins from $1$.

Define $g(i,j)$ as follows:

• $g(i,j)$ is the largest integer $x$ that satisfies ${a_p:i\le p\le j}\subseteq{a_q:x\le q\le j}$ while $i \le j$;
• and $g(i,j)=0$ while $i \gt j$.

There are $q$ queries. For each query you are given four integers $l,r,x,y$, you need to calculate $\sum\limits_{i=l}^{r}\sum\limits_{j=x}^{y}g(i,j)$.

洛天依给你一个包含 $n$ 个整数的数组 $a$，数组下标从 $1$ 开始。

定义函数 $g(i,j)$ 如下：

• 当 $i \le j$ 时，$g(i,j)$ 是满足 $\{a_p \mid i\le p\le j\} \subseteq \{a_q \mid 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)$。

The first line contains two integers $n$ and $q$ ($1\le n,q\le 10^6$) — the length of the array $a$ and the number of queries.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$) — the elements of the array $a$.

Next $q$ lines describe a query. The $i$-th line contains four integers $l,r,x,y$ ($1\le l\le r\le n, 1\le x\le y\le n$) — the integers in the $i$-th query.

第一行包含两个整数 $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$ 次查询中的参数。

Print $q$ lines where $i$-th line contains one integer — the answer for the $i$-th query.

输出 $q$ 行，其中第 $i$ 行包含一个整数——即第 $i$ 个查询的答案。

In the first example:

In the first query, the answer is $g(1,4)+g(1,5)=3+3=6$.

$x=1,2,3$ can satisfies ${a_p:1\le p\le 4}\subseteq{a_q:x\le q\le 4}$, $3$ is the largest integer so $g(1,4)=3$.

In the second query, the answer is $g(2,3)+g(3,3)=3+3=6$.

In the third query, the answer is $0$, because all $i \gt j$ and $g(i,j)=0$.

In the fourth query, the answer is $g(6,6)=6$.

In the second example:

In the second query, the answer is $g(2,3)=2$.

In the fourth query, the answer is $g(1,4)+g(1,5)=2+2=4$.

在第一个例子中：

第一个查询的答案是 $g(1,4)+g(1,5)=3+3=6$。

满足 $\{a_p:1\le p\le 4\}\subseteq\{a_q:x\le q\le 4\}$ 的 $x$ 可取 $1,2,3$，其中最大的整数为 $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$。