let rec lower_bound l r p =
  if r <= 1 + l
  then r
  else let m = (l + r) / 2 in
       if p m
       then lower_bound l m p
       else lower_bound m r p

let rec upper_bound l r p =
  if r <= 1 + l
  then l
  else let m = (l + r) / 2 in
       if p m 
       then upper_bound m r p
       else upper_bound l m p

let () = Scanf.scanf "%d\n" @@ fun n ->
  let xs = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun x -> x in
  Scanf.scanf "%d\n" @@ fun l ->
  let up = Array.make_matrix 32 n 0 in
  let dn = Array.make_matrix 32 n 0 in
  for i = 0 to n - 1 do
    up.(0).(i) <- upper_bound 0 n (fun j -> xs.(j) - xs.(i) <= l);
    dn.(0).(i) <- lower_bound (-1) (n - 1) (fun j -> xs.(i) - xs.(j) <= l)
  done;
  for i = 1 to 31 do
    for j = 0 to n - 1 do
      up.(i).(j) <- up.(i - 1).(up.(i - 1).(j));
      dn.(i).(j) <- dn.(i - 1).(dn.(i - 1).(j))
    done
  done;
  Scanf.scanf "%d\n" @@ fun q ->
  for i = 0 to q - 1 do
    Scanf.scanf "%d %d\n" @@ fun a b ->
      Printf.printf "%d\n" @@ succ @@ snd @@
        Array.fold_left 
        ( if a < b then
            fun (a, acc) i ->
              if b - 1 <= up.(i).(a)
              then (a, acc)
              else (up.(i).(a), acc lor (1 lsl i))
          else 
            fun (a, acc) i ->
              if dn.(i).(a) <= b - 1
              then (a, acc)
              else (dn.(i).(a), acc lor (1 lsl i)) ) (a - 1, 0) @@
        Array.init 32 @@ fun i -> 31 - i
  done
