В компьютерной игре «Мегапрыжок» герой прыгает между вершинами горной цепи с целью попасть на точку с флагом, где завершается уровень.
Горная цепь в игре состоит из $$$n$$$ подряд идущих зубцов, $$$i$$$-й из которых находится в позиции $$$i$$$ и имеет высоту $$$h_i$$$. При этом для любых $$$i \lt j$$$ герой может прыгнуть по прямой с зубца $$$i$$$ на зубец $$$j$$$, при условии, что во время полёта по прямой на его пути не будет других зубцов. Более формально, не найдётся такого $$$k$$$, что $$$i \lt k \lt j$$$ и вершина $$$k$$$-го зубца — точка с координатами $$$(k, h_k)$$$ — находится строго выше отрезка, соединяющего точки $$$(i, h_i)$$$ и $$$(j, h_j)$$$.
Компания «Победи ИИ» занимается тренировкой нейросети для управления героем в этой игре. Для создания тренировочных данных необходимо ответить на несколько запросов: для пары индексов $$$l, r$$$ $$$(1 \le l \le r \le n)$$$ выяснить, за какое минимальное число прыжков, начав на зубце с номером $$$l$$$, герой сможет попасть на зубец с номером $$$r$$$.
В первой строке входных данных находится число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — число зубцов.
Во второй строке находятся $$$n$$$ чисел: $$$h_1, h_2, \dots, h_n$$$ $$$(0 \le h_i \le 10^{12})$$$ — высоты зубцов.
В третьей строке находится число $$$q$$$ $$$(1 \le q \le 10^5)$$$ — количество запросов.
В каждой из следующих $$$q$$$ строк находятся два числа $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ — параметры очередного запроса.
Для каждого запроса в отдельной строке выведите целое неотрицательное число минимальное необходимое число прыжков.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 9 | $$$n, q \le 300$$$ | — |
| 2 | 9 | $$$n, q \le 5000$$$ | 1 |
| 3 | 14 | $$$h_i \le 10$$$ | — |
| 4 | 21 | Существует $$$k$$$, такое что для всех $$$i$$$ выполнено $$$l_i \le k \le r_i$$$ | — |
| 5 | 27 | $$$n, q \le 5 \cdot 10^4$$$ | 1, 2 |
| 6 | 20 | включает подзадачи 1–5 | 1–5 |
8 5 3 4 3 6 2 1 4 3 1 8 2 7 4 4
2 2 0
Разберём второй запрос в примере из условия. Путь героя от зубца 2 до зубца 7 может выглядеть следующим образом:
