let rec loop x fn =
  match fn x with
  | `Break x -> x
  | `Continue x -> loop x fn

let ( |- ) x f = f x; x

module List = struct
  include List
  let take n lst =
    loop (0, lst, []) begin fun (i, rest, r_acc) ->
      match i < n, rest with
      | true, []  | false, _ -> `Break (rev r_acc)
      | true, x :: rest -> `Continue (i + 1, rest, x :: r_acc) end
  let drop n lst =
    loop (0, lst) begin fun (i, rest) ->
      match i < n, rest with
      | true, _ :: rest -> `Continue (i + 1, rest)
      | true, []  | false, _ -> `Break rest end

  let map fn lst =
    loop (lst, []) begin fun (lst, r_acc) ->
      match lst with
      | [] -> `Break (rev r_acc)
      | x :: rest -> `Continue (rest, fn x :: r_acc) end
end

let () =
  let open Scanf in
  let read_ints () = let open Buffer in
    let buf = create 10 in
    let add = add_bytes buf and get () = contents buf in
    loop () begin fun () ->
      try read_line () ^ " " |> add; `Continue ()
      with _ -> `Break (get ()) end
    |> Str.(split (regexp " ")) |> List.map int_of_string in

  let rest = read_ints () in
  let n, rest = match rest with
    | [] -> assert false  | n :: rest -> n, rest in
  let xs = List.take n rest in
  let l, q, qs = match List.drop n rest with
    | [] | [_] -> assert false  | l :: q :: qs -> l, q, qs in
  let qs =
    let qs = qs |> List.map (fun q -> q - 1) in
    loop (qs, []) begin fun (rest, r_acc) ->
      match rest with
      | x:: y:: rest -> `Continue (rest, (x, y):: r_acc)
      | []  | _:: [] -> `Break (List.rev r_acc) end in
  (* input stage is finally finished *)

  let xs = Array.of_list xs in
  let bisect fn_shift fn_idx = fun l r x ->
    loop (l, r) begin fun (l, r) ->
      if r - l - 1 = 0 then `Break (fn_idx l r)
      else let m = (l + r) / 2 in
        match fn_shift x xs.(m) with
        | `Left -> `Continue (l, m)
        | `Right -> `Continue (m, r) end in
  let bisect_l = bisect
      (fun x m -> if x < m then `Left else `Right) (fun l r -> l)
  and bisect_r = bisect
      (fun x m -> if x > m then `Right else `Left) (fun l r -> r) in

  let max_step = 10 in
  let next = let open Bigarray in
    let memo = Array3.create Int c_layout n 2 (max_step + 1) in
    let fn_dir = function `Left -> 0  | `Right -> 1 in
    let cache = fun (here, dir, step) ->
      fun x -> memo.{here, fn_dir dir, step} <- x
    and get = fun (here, dir, step) ->
      memo.{here, fn_dir dir, step} in
    for here = 0 to n - 1 do
      let x' = xs.(here) + l in
      let next = bisect_l here n x' in
      cache (here, `Right, 0) next;

      let here = n - 1 - here in
      let x' = xs.(here) - l in
      let next = bisect_r (-1) here x' in
      cache (here, `Left, 0) next;
    done;
    for step = 1 to max_step do
      for here = 0 to n - 1 do
        try
          let get_ x = get (x, `Right, step - 1) in
          let next = get_ (get_ here) in
          cache (here, `Right, step) next;

          let here = n - 1 - here in
          let get_ x = get (x, `Left, step - 1) in
          let next = get_ (get_ here) in
          cache (here, `Left, step) next;
        with e ->
          Printf.printf "here:%d, step:%d\n" here step;
          raise e
      done
    done;
    get in

  let ( ** ) a b = int_of_float ((float_of_int a) ** 
                                 (float_of_int b)) in
  let rec solve (a, b): int =
    let reached, next=
      if a < b
      then (fun x -> b <= x),
           (fun x step -> next (x, `Right, step))
      else (fun x -> b >= x),
           (fun x step -> next (x, `Left, step)) in
    let step =
      loop max_step begin fun step ->
        let a' = next a step in
        match step = 0, reached a' with
        | true, _ -> `Break 0
        | false, true -> `Continue (step - 1)
        | false, false -> `Break step end in
    let a' = next a step in
    if reached a'
    then 2 ** step
    else 2 ** step + solve (a', b) in

  qs |> List.map begin fun q ->
    Printf.printf "%d\n" (solve q);
  end |> ignore;


Measured memory_bytes: 40224