アリスとボブは別々の世界に住んでいます。どれほど深く交信を望んでも、宇宙は無関心な沈黙で応えるだけです。二つの世界の間には広大で静かな境界が横たわり、そこに $n$ 個の古代のゲートが一列に並んでいます。これらのゲートは何千年も休眠していましたが、ある日、アリスとボブの願いに動かされたかのように、目覚め始めます。

$i$ 番目のゲートは日 $p_i$ に目覚めます。同じ日に目覚めるゲートは二つとありません。したがって、数列 $p_1, p_2, \ldots, p_n$ は $\{1,2,\ldots,n\}$ の順列です。

目覚めたゲートが一つだけでは、それは現実に生じた孤独な裂け目にすぎません。かすかなささやきを運ぶことはあっても、虚空を橋渡しすることはできません。ゲートの連続区間がアリスとボブにとって真の経路となるためには、その区間内に少なくとも二つのゲートが目覚めていなければなりません。そうして初めて、世界の間の空間が安定し、彼らのメッセージが安全に行き交うことができるのです。

任意のゲートの添字 $i

$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$) が含まれます。

二行目には、$\{1,2,\ldots,n\}$ の順列をなす $n$ 個の整数 $p_1,p_2,\ldots,p_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$ です。