B. Also Try Minecraft
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы занимаетесь бета-тестированием нового секретного обновления игры Terraria. Это обновление добавит в игру квесты!

Для простоты карту мира можно представить как массив длины $$$n$$$, где $$$i$$$-й столбец мира имеет высоту $$$a_i$$$.

Вам необходимо протестировать $$$m$$$ квестов. Квест с номером $$$j$$$ представлен двумя целыми числами $$$s_j$$$ и $$$t_j$$$. В этом квесте вам необходимо добраться из столбца $$$s_j$$$ до столбца $$$t_j$$$. В начале квеста вы появляетесь в столбце $$$s_j$$$.

За один ход вы можете перейти из столбца $$$x$$$ в столбец $$$x-1$$$ или в столбец $$$x+1$$$. В этой версии у вас есть Spectre Boots, которые позволяют вам летать. Так как это бета-версия, эти ботинки работают неправильно, поэтому они позволяют вам летать только тогда, когда вы движетесь вверх, и имеют бесконечную длительность полета. Когда вы перемещаетесь из столбца с высотой $$$p$$$ в столбец с высотой $$$q$$$, вы получаете какое-то количество урона от падения. Если высота $$$p$$$ больше высоты $$$q$$$, вы получаете $$$p - q$$$ единиц урона от падения, иначе вы летите вверх и получаете $$$0$$$ единиц урона.

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

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^5; 1 \le m \le 10^5$$$) — количество столбцов в мире и количество квестов, которые вам надо протестировать, соответственно.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ равно высоте $$$i$$$-го столбца мира.

Следующие $$$m$$$ строк описывают квесты. В $$$j$$$-й из них содержатся два целых числа $$$s_j$$$ и $$$t_j$$$ ($$$1 \le s_j, t_j \le n; s_j \ne t_j$$$), которые значат, что вам необходимо переместиться из столбца $$$s_j$$$ в столбец $$$t_j$$$ в течение $$$j$$$-го квеста.

Заметьте, что $$$s_j$$$ может быть больше, чем $$$t_j$$$.

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

Выведите $$$m$$$ строк. В $$$j$$$-й из них должно находиться минимальное количество урона от падения, который вы можете получить во время выполнения $$$j$$$-го квеста.

Пример
Входные данные
7 6
10 8 9 6 8 12 7
1 2
1 7
4 6
7 1
3 5
4 2
Выходные данные
2
10
0
7
3
1