Вы занимаетесь бета-тестированием нового секретного обновления игры 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\) единиц урона.
Для каждого из заданных квестов определите минимальное количество урона от падения, которое вы можете получить, выполняя этот квест.
Выходные данные
Выведите \(m\) строк. В \(j\)-й из них должно находиться минимальное количество урона от падения, который вы можете получить во время выполнения \(j\)-го квеста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|