Gromozeka has the following two personal principles: he never travels more than
L in one day. He never sleeps outdoors. That is, he must be at the hotel at the end of the day.
The Planet Blue has
N hotels and all are located on the same street. The coordinate of the
ith hotel (1<=i<=N) is
xi.
Traveling around the planet Bluk, Gromozeka planned
Q moves. With each move he plans to change hotel
aj to
bj (1<=j<= Q). For each move, find the minimum number of days Gromozeka needs to get from the
ajth hotel to the
bjth, following his principles.
It is guaranteed that he can always travel from the
ajth hotel to the
bjth th hotel.< br />
Input
The first line contains an integer N (2<=N<=10
5) - the number of hotels on the planet Bluk. The second line contains N numbers
xi - coordinates of the i-th hotel (1<=x
1<x
2< /sub><...<xN<=109 , xi+1−x i<=L). The third line contains the number L (1<=L<=109). The fourth line contains the number Q (1<=N<=105).
The last Q lines contain two different numbers aj and bj (1<=aj,bj<=N). All numbers are integers.
Imprint
Print Q lines. The j-th line (1<=j<=Q) should contain the minimum number of days Gromozeka needs to get from aj-th hotel to bj-th hotel.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
9
1 3 6 13 15 18 19 29 31
10
4
18
7 3
67
8 5 |
4
2
1
2 |
On the 1st crossing, he can travel from the 1st hotel to the 8th in 4 days as follows:
Day 1: Transfer from the 1st hotel to the 2nd hotel. Distance traveled - 2.
Day 2: Transfer from the 2nd hotel to the 4th. Distance traveled - 10.
Day 3: Transfer from the 4th hotel to the 7th. Distance traveled - 6.
Day 4: Transfer from the 7th hotel to the 8th. Distance traveled - 10. |