Alice 和 Bob 分別住在不同的世界。無論他們多麼渴望交流，宇宙只以冷漠的沉默回應。在他們的世界之間，存在著一片廣闊而寧靜的邊境，那裡有 $n$ 座古老的大門排成一列。這些大門沉睡了數千年，直到有一天，或許是被 Alice 和 Bob 的願望所感動，它們開始甦醒。
第 $i$ 座大門在 $p_i$ 天甦醒。沒有兩座大門在同一天甦醒；因此，數列 $p_1,p_2,\ldots,p_n$ 是 $\{1,2,\ldots,n\}$ 的一個排列。
單一的甦醒大門只是現實中的一道孤獨裂縫。它或許承載著轉瞬即逝的低語，但無法跨越虛空。要讓一段連續的門區間成為 Alice 和 Bob 真正的通道，該區間內至少要有兩座甦醒的大門。只有這樣，兩個世界之間的空間才能足夠穩定，讓他們的訊息安全地穿越。
對於任意門的編號 $i 給定 $q$ 個查詢。每個查詢由一個區間 $[L,R]$ 定義。對於每個查詢，計算所有完全包含在 $[L,R]$ 內的連續子區間（長度至少為 $2$）首次能夠承載他們訊息的那一天的總和： $$
\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]$ 內長度至少為 $2$ 的子數組的第二最小值分別為 $3,3,2,4,2,4$，因此答案為 $18$。輸入格式
輸出格式
範例
輸入 1
4 4
3 1 4 2
1 4
2 4
1 2
3 3
輸出 1
18
10
3
0
說明