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:

* He never travels a distance of more than L in a single day.
* He never sleeps in the open. That is, he must stay at a hotel at the end of a day.



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.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq L \leq 10^9
* 1 \leq Q \leq 10^5
* 1 \leq x_i < x_2 < ... < x_N \leq 10^9
* x_{i+1} - x_i \leq L
* 1 \leq a_j,b_j \leq N
* a_j \neq b_j
* N,\,L,\,Q,\,x_i,\,a_j,\,b_j are integers.

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


Output

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.

Example

Input

9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5


Output

4
2
1
2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.Exception;
import java.util.Arrays;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		long[] x = new long[n];

		String[] tempX = br.readLine().split(" ");
		for (int i = 0; i < n; i++) 
			x[i] = Long.parseLong(tempX[i]);
		

		long l = Long.parseLong(br.readLine());
		int q = Integer.parseInt(br.readLine());

		int[] aa = new int[q];
		int[] bb = new int[q];

		for (int i = 0; i < q; i++) {
			String[] temp = br.readLine().split(" ");
			aa[i] = Integer.parseInt(temp[0])-1;
			bb[i] = Integer.parseInt(temp[1])-1;
		}


		int[][] dp = new int[n][17];
		int[] length = new int[n];


		int j = Math.abs(Arrays.binarySearch(x, x[0]+l)+1);
		int limit = 0;
		for (int i = 0; i < n; i++) {
			long bound = x[i] + l;
			for (; j < n && x[j] <= bound; j++);
			if (j == n) {
				limit = i;
				break;
			}
			else {
				dp[i][0] = j-1;
				length[i] = 1;
			}
		}

		for (int d = 0; limit > 0; d++) {
			for (int i = 0; i < limit; i++) {
				int t = dp[i][d];
				if (t < limit) {
					dp[i][d+1] = dp[t][d];
					length[i] += 1;
				}
				else {
					limit = i;
					break;
				}
			}
		}

		for (int i = 0; i < q; i++) {
			int a = aa[i];
			int b = bb[i];
			if (a > b) {
				int temp = a;
				a = b;
				b = temp;
			}

			int p = Math.abs(Arrays.binarySearch(dp[a], 0, length[a], b)+1) - 1;
			int cnt = 0;
			while (p >= 0) {
				cnt |= 1 << p;
				a = dp[a][p];
				p = Math.abs(Arrays.binarySearch(dp[a], 0, length[a], b)+1) - 1;
			}

			if (a < b)
				cnt++;
			System.out.println(cnt);
		}

	}
}