Yuto i Platina zamierzają zagrać w grę "Non-Decreasing Subarray Game". Gra toczy się na tablicy $A$ o długości $N$.

Yuto najpierw podaje liczbę całkowitą, a następnie Platina podaje liczbę całkowitą. Liczby wybrane przez graczy muszą znajdować się w przedziale od $L$ do $R$ włącznie. Niech wybrane liczby całkowite to $a$ oraz $b$, uporządkowane w taki sposób, że $a \le b$. Wówczas wynikiem uzyskanym w grze jest liczba par $(i, j)$ takich, że $a \le i \le j \le b$ oraz przedział $[i, j]$ tworzy niemalejący podciąg w tablicy $A$.

Mówimy, że $[i, j]$ tworzy niemalejący podciąg, gdy dla każdego $x$ i $y$ takich, że $i \le x \le y \le j$, prawdą jest, że $A[x] \le A[y]$.

Yuto chce zminimalizować wynik, a Platina chce go zmaksymalizować. Ta gra jest tak fascynująca, że rozegramy ją $T$ razy. Wszystkie gry wykorzystują tę samą tablicę $A$, ale w różnych grach mogą być użyte różne wartości $L$ i $R$.

Zakładając, że obaj gracze grają optymalnie, znajdź liczbę punktów, które uzyskają w każdej z rozegranych gier.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $N$ oraz $T$ ($1 \le N, T \le 500\,000$): długość tablicy oraz liczbę rozegranych gier.

W drugiej linii podane są wartości tablicy $A[1], A[2], A[3], \dots, A[N]$ ($1 \le A[i] \le 10^9$).

Każda z kolejnych $T$ linii opisuje grę za pomocą dwóch liczb całkowitych $L_i$ oraz $R_i$ ($1 \le L_i \le R_i \le N$): wartości $L$ i $R$ użytych w danej grze.

Wyjście

Dla każdej gry wypisz wynik uzyskany w tej grze w osobnej linii.

Przykład

Wejście 1

8 5
7 10 3 1 9 5 5 2
1 5
2 2
5 8
1 8
3 5

Wyjście 1

4
1
4
7
3