У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше L за один день. Он никогда не спит под открытым небом. То есть он должен находться в отеле в конце дня.
На планете Блук N отелей и все расположены на одной улице. Координата i-го отеля (1<=i<=N) равна xi.
Путешествуя по планете Блук, Громозека запланировал Q переездов. Каждым переездом он планирует менять отель aj на bj (1<=j<=Q). Для каждого переезда найдите минимальное количество дней, которое нужно Громозеке, чтобы добраться от aj-го отеля до bj-го, следуя его принципам.
Гарантируется, что он всегда может поехать из aj-го отеля до bj-го отеля.
Входные данные
В первой строке задается целое число N (2<=N<=105) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x1<x2<...<xN<=109 , xi+1−xi<=L). В третьей строке записано число L (1<=L<=109). В четвертой строке - число Q (1<=N<=105).
В последних Q строчках находится по два различных числа aj и bj (1<=aj,bj<=N). Все числа целые.
Выходные данные
Выведите Q строк. В j-й строке (1<=j<=Q) должно быть указано минимальное количество дней, которое Громозеке нужно, чтобы добраться из aj-го отеля до bj -го отеля.