Score : 700 points
N hotels are located on a straight line. The coordinate of the i-th hotel (1 \leq i \leq N) is x_i.
Tak the traveler has the following two personal principles:
You are given Q queries. The j-th (1 \leq j \leq Q) query is described by two distinct integers a_j and b_j. For each query, find the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel following his principles. It is guaranteed that he can always travel from the a_j-th hotel to the b_j-th hotel, in any given input.
The input is given from Standard Input in the following format:
N x_1 x_2 ... x_N L Q a_1 b_1 a_2 b_2 : a_Q b_Q
Print Q lines. The j-th line (1 \leq j \leq Q) should contain the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel.
9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5
4 2 1 2
For the 1-st query, he can travel from the 1-st hotel to the 8-th hotel in 4 days, as follows: