У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше
L за один день. Он никогда не спит под открытым небом. То есть он должен находться в отеле в конце дня.
На планете Блук
N отелей и все расположены на одной улице. Координата
i-го отеля (1<=i<=N) равна
xi.
Путешествуя по планете Блук, Громозека запланировал
Q переездов. Каждым переездом он планирует менять отель
aj на
bj (1<=j<=Q). Для каждого переезда найдите минимальное количество дней, которое нужно Громозеке, чтобы добраться от
aj-го отеля до
bj-го, следуя его принципам.
Гарантируется, что он всегда может поехать из
aj-го отеля до
bj-го отеля.
Входные данные
В первой строке задается целое число N (2<=N<=10
5) - количество отелей на планете Блук. Во второй строке - N чисел
xi - координаты i-го отеля (1<=x
1<x
2<...<x
N<=10
9 , x
i+1−x
i<=L). В третьей строке записано число L (1<=L<=10
9). В четвертой строке - число Q (1<=N<=10
5).
В последних Q строчках находится по два
различных числа
aj и
bj (1<=a
j,b
j<=N). Все числа целые.
Выходные данные
Выведите Q строк. В j-й строке (1<=j<=Q) должно быть указано минимальное количество дней, которое Громозеке нужно, чтобы добраться из
aj-го отеля до
bj -го отеля.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5 |
4
2
1
2 |
По 1-му переезду он может проехать от 1-го отеля до 8-го за 4 дня следующим образом:
День 1: Переезд из 1-го отеля во 2-й отель. Пройденное расстояние - 2.
День 2: Переезд из 2-го отеля в 4-й. Пройденное расстояние - 10.
День 3: Переезд из 4-го отеля в 7-й. Пройденное расстояние - 6.
День 4: Переезд из 7-го отеля в 8-й. Пройденное расстояние - 10. |