Alicja i Bob żyją w oddzielnych światach. Nieważne, jak bardzo pragną się porozumieć, wszechświat odpowiada tylko obojętnym milczeniem. Pomiędzy ich światami rozciąga się rozległa, cicha granica, na której w rzędzie stoi $n$ starożytnych bram. Bramy te spały przez tysiąclecia, aż pewnego dnia, być może poruszone pragnieniami Alicji i Boba, zaczynają się budzić.

$i$-ta brama budzi się w dniu $p_i$. Żadne dwie bramy nie budzą się tego samego dnia; zatem ciąg $p_1,p_2,\ldots,p_n$ jest permutacją zbioru $\{1,2,\ldots,n\}$.

Pojedyncza obudzona brama to jedynie samotne pęknięcie w rzeczywistości. Może nieść ulotny szept, ale nie jest w stanie przerzucić mostu przez pustkę. Aby ciągły odcinek bram utworzył prawdziwą ścieżkę dla Alicji i Boba, co najmniej dwie bramy w nim muszą być obudzone. Tylko wtedy przestrzeń między światami stabilizuje się na tyle, by ich wiadomości mogły bezpiecznie przejść.

Dla dowolnych indeksów bram $i

Dane jest $q$ zapytań. Każde zapytanie jest określone przez przedział $[L,R]$. Dla każdego zapytania oblicz sumę dokładnych dni, w których każdy prawidłowy ciągły pododcinek w całości zawarty w $[L,R]$ po raz pierwszy staje się zdolny do przenoszenia ich wiadomości:

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

Jeśli $L=R$, to nie ma odcinka zawierającego co najmniej dwie bramy, więc odpowiedzią jest $0$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $q$ ($1 \le n,q \le 2\cdot 10^5$).

Drugi wiersz zawiera $n$ liczb całkowitych $p_1,p_2,\ldots,p_n$ stanowiących permutację zbioru $\{1,2,\ldots,n\}$.

Każdy z kolejnych $q$ wierszy zawiera dwie liczby całkowite $L$ i $R$ ($1 \le L \le R \le n$), opisujące zapytanie.

Wyjście

Wypisz $q$ wierszy. $t$-ty wiersz musi zawierać odpowiedź na $t$-te zapytanie.

Przykład

Wejście 1

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

Wyjście 1

18
10
3
0

Uwagi

Dla pierwszego zapytania pododcinki długości co najmniej $2$ wewnątrz $[1,4]$ mają drugie minimum równe odpowiednio $3,3,2,4,2,4$, więc odpowiedzią jest $18$.