爱丽丝和鲍勃生活在不同的世界。无论他们多么渴望交流，宇宙只以漠然的沉默回应。在两个世界之间，有一道广阔而寂静的边界，那里 $n$ 座古老的大门排成一列。这些大门沉睡了数千年，直到有一天，也许是受到爱丽丝和鲍勃愿望的触动，它们开始苏醒。

第 $i$ 座大门在 $p_i$ 日苏醒。没有两座大门在同一天苏醒；因此，序列 $p_1,p_2,\ldots,p_n$ 是 $\{1,2,\ldots,n\}$ 的一个排列。

单座苏醒的大门只是现实中的一道孤独裂缝。它或许能承载短暂的耳语，但不足以跨越虚空。要让连续的一段大门成为爱丽丝和鲍勃真正的通道，其中至少要有两座大门苏醒。只有这样，两个世界之间的空间才能足够稳定，让他们的信息安全穿过。

对于任意门索引 $i< j$，令 $\operatorname{sec}(i,j)$ 定义为从 $i$ 到 $j$ 的连续大门段首次包含至少两座苏醒大门的准确日期。等价地，$\operatorname{sec}(i,j)$ 是 $p_i,p_{i+1},\ldots,p_j$ 中第二小的值。

给定 $q$ 个询问。每个询问由一个区间 $[L,R]$ 定义。对于每个询问，计算完全包含在 $[L,R]$ 内的每个有效连续子段首次能够传递消息的日期之和：

$$ \sum_{L \le i < j \le R} \operatorname{sec}(i,j). $$

如果 $L=R$，则不存在包含至少两座大门的段，因此答案为 $0$。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n,q \le 2\cdot 10^5$）。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，构成 $\{1,2,\ldots,n\}$ 的一个排列。

接下来的 $q$ 行，每行包含两个整数 $L$ 和 $R$（$1 \le L \le R \le n$），描述一个询问。

输出格式

输出 $q$ 行。第 $t$ 行必须包含第 $t$ 个询问的答案。

样例

输入 1

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

输出 1

18
10
3
0

说明

对于第一个询问，$[1,4]$ 内部长度至少为 $2$ 的子数组的第二小值分别为 $3,3,2,4,2,4$，因此答案为 $18$。