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
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 next = let open Hashtbl in
    let memo = create 10 in
    let cache = replace memo and get = find memo in
    let calc init fn_bound direction fn_step fn_shift fn_bisect =
      loop init begin fun here ->
        match fn_bound here with
        | false ->
          cache (here, direction) (fn_step here); `Break ()
        | true ->
          let x' = fn_shift xs.(here) l in
          let next = fn_bisect here x' in
          cache (here, direction) next;
          `Continue (fn_step here) end in
    calc 0 (fun x -> x < n - 1) `Right succ ( + )
      (fun here x -> bisect_l here n x);
    calc (n - 1) (fun x -> x > 0) `Left pred ( - )
      (fun here x -> bisect_r (-1) here x);
    get in

  let module Memo = struct
    let cache, cached, get = let open Hashtbl in
      let memo = create 10 in
      let cache = replace memo and get = find memo
      and cached = mem memo in
      cache, cached, get
  end in

  let add, get = let open Buffer in
    let buf = create (q * 2) in
    let add = add_string buf and get () = contents buf in
    add, get in

  let rec solve ((a, b) as arg): int =
    let open Memo in
    if cached arg then get arg
    else
      let reached, next =
        if a < b
        then (fun x -> b <= x), (fun x -> next (x, `Right))
        else (fun x -> b >= x), (fun x -> next (x, `Left)) in
      let a' = next a in
      if reached a' then 1
      else 1 + solve (a', b) |- cache arg in

  qs |> List.map begin fun q ->
    let open Printf in
    add (sprintf "%d\n" (solve q));
  end |> ignore;
  Printf.printf "%s" (get ());
