Alice et Bob résident dans des mondes séparés. Peu importe à quel point ils aspirent à communiquer, l'univers ne répond que par un silence indifférent. Entre leurs mondes s'étend une vaste et tranquille frontière où $n$ portes anciennes sont alignées. Ces portes sont restées endormies pendant des millénaires jusqu'au jour où, peut-être émues par les souhaits d'Alice et Bob, elles commencent à s'éveiller.

La $i$-ème porte s'éveille le jour $p_i$. Deux portes ne s'éveillent jamais le même jour ; ainsi, la séquence $p_1,p_2,\ldots,p_n$ est une permutation de $\{1,2,\ldots,n\}$.

Une seule porte éveillée n'est qu'une fracture solitaire dans la réalité. Elle peut porter un murmure fugace, mais elle ne peut franchir le vide. Pour qu'un segment continu de portes forme un véritable chemin pour Alice et Bob, au moins deux portes à l'intérieur doivent être éveillées. Ce n'est qu'alors que l'espace entre les mondes se stabilise suffisamment pour que leurs messages puissent traverser en toute sécurité.

Pour tout couple d'indices de portes $i

On vous donne $q$ requêtes. Chaque requête est définie par un intervalle $[L,R]$. Pour chaque requête, calculez la somme des jours exacts où chaque sous-segment continu valide entièrement contenu dans $[L,R]$ devient capable de transporter leurs messages :

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

Si $L=R$, il n'y a aucun segment contenant au moins deux portes, donc la réponse est $0$.

Entrée

La première ligne contient deux entiers $n$ et $q$ ($1 \le n,q \le 2\cdot 10^5$).

La deuxième ligne contient $n$ entiers $p_1,p_2,\ldots,p_n$ formant une permutation de $\{1,2,\ldots,n\}$.

Chacune des $q$ lignes suivantes contient deux entiers $L$ et $R$ ($1 \le L \le R \le n$), décrivant une requête.

Sortie

Affichez $q$ lignes. La $t$-ème ligne doit contenir la réponse à la $t$-ème requête.

Exemples

Entrée 1

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

Sortie 1

18
10
3
0

Remarque

Pour la première requête, les sous-tableaux de longueur au moins $2$ à l'intérieur de $[1,4]$ ont pour deuxièmes minimums $3,3,2,4,2,4$, donc la réponse est $18$.