Прыжки по вершинам
(Время: 5 сек. Память: 64 Мб Сложность: 70%)
В компьютерной игре «Мегапрыжок» герой прыгает между вершинами горной цепи с целью
попасть на точку с флагом, где завершается уровень.
Горная цепь в игре состоит из n подряд идущих зубцов, i-й из которых находится в позиции i и
имеет высоту hi. При этом для любых i < j герой может прыгнуть по прямой с зубца i на зубец j,
при условии, что во время полёта по прямой на его пути не будет других зубцов. Более формально,
не найдётся такого k, что i < k < j и вершина k-го зубца – точка с координатами (k, hk) – находится
строго выше отрезка, соединяющего точки (i, hi) и (j, hj).
Компания «Победи ИИ» занимается тренировкой нейросети для управления героем в этой игре.
Для создания тренировочных данных необходимо ответить на несколько запросов: для пары индексов l, r (1 ≤ l ≤ r ≤ n) выяснить, за какое минимальное число прыжков, начав на зубце с номером l, герой сможет попасть на зубец с номером r.
Входные данные
В первой строке входного файла INPUT.TXT находится число n (1 ≤ n ≤ 105) – число зубцов.
Во второй строке находятся n чисел: h1, h2, ..., hn (0 ≤ hi ≤ 1012) – высоты зубцов.
В третьей строке находится число q (1 ≤ q ≤ 105) – количество запросов.
В каждой из следующих q строк находятся два числа li, ri (1 ≤ li ≤ ri ≤ n) – параметры очередного запроса.
Выходные данные
Для каждого запроса в отдельной строке выходного файла OUTPUT.TXT выведите целое неотрицательное число – минимальное необходимое число прыжков.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8
5 3 4 3 6 2 1 4
3
1 8
2 7
4 4 | 2
2
0 |
Примечание
Разберём второй запрос в примере из условия. Путь героя от зубца 2 до зубца 7 может выглядеть следующим образом:
Он посетит вершины 2, 5 и 7, совершив два прыжка.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
