Юто и Платина собираются сыграть в игру «Неубывающий подмассив». Игра проводится на массиве $A$ длины $N$.

Сначала Юто называет целое число, а затем Платина называет целое число. Числа, выбранные игроками, должны находиться в интервале от $L$ до $R$ включительно. Пусть выбранные целые числа равны $a$ и $b$, упорядоченные так, что $a \le b$. Тогда счетом в игре является количество пар $(i, j)$ таких, что $a \le i \le j \le b$, а интервал $[i, j]$ образует неубывающий подмассив в массиве $A$.

Мы говорим, что $[i, j]$ образует неубывающий подмассив, если для любых $x$ и $y$ таких, что $i \le x \le y \le j$, выполняется условие $A[x] \le A[y]$.

Юто хочет минимизировать счет, а Платина хочет его максимизировать. Эта игра настолько увлекательна, что мы собираемся сыграть в нее $T$ раз. Во всех играх используется один и тот же массив $A$, но в разных играх могут использоваться разные значения $L$ и $R$.

Предполагая, что оба игрока играют оптимально, найдите количество очков, которое они получат в каждой из сыгранных игр.

Входные данные

В первой строке содержатся два целых числа $N$ и $T$ ($1 \le N, T \le 500\,000$): длина массива и количество сыгранных игр соответственно.

Во второй строке заданы значения массива $A[1], A[2], A[3], \dots, A[N]$ ($1 \le A[i] \le 10^9$).

Каждая из следующих $T$ строк описывает игру двумя положительными целыми числами $L_i$ и $R_i$ ($1 \le L_i \le R_i \le N$): значения $L$ и $R$, используемые для этой игры.

Выходные данные

Для каждой игры выведите счет в этой игре на отдельной строке.

Примеры

Входные данные 1

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

Выходные данные 1

4
1
4
7
3