(*
 * forall l r (p : forall n, l < n <= r -> bool),
 *   ( exists m,
 *     l < m <= r /\ forall n H, p n H = true <-> m <= n ) ->
 *   { m |
 *     l < m <= r /\ forall n H, p n H = true <-> m <= n }
 *)
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

(*
 * forall l r (p : forall n, l <= n < r -> bool),
 *   ( exists m,
 *     l <= m < r /\ forall n H, p n H = true <-> n <= m ) ->
 *   { m |
 *     l <= m < r /\ forall n H, p n H = true <-> n <= m }
 *)
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 as_ = Array.init n @@ fun _ ->
    Scanf.scanf "%d " @@ fun a -> a in
  let sum_as = Array.make (n + 1) 0 in
  (* sum_as.(i): 添字の範囲[0; i)におけるas_の要素の総和 *)
  (* 添字の範囲[i; j)の総和が欲しければ sum_as.(j) - sum_as.(i) で手に入る *)
  for i = 0 to n - 1 do
    sum_as.(i + 1) <- as_.(i) + sum_as.(i)
  done;
  begin
    List.concat @@ List.map (fun b1 ->
      List.concat @@ List.map (fun b2 ->
        (* 真ん中の切れ目だけ与えてやる *)
        Array.to_list @@ Array.init (n - 3) (fun j ->
          let j = j + 2 in
          (* B は[0; i)，C は[i; j)，D は[j; k)，E は[k; n) *)
          (* PとQどちらを大きくするかをb1に委ね，にぶたんする *)
          let i =
            if b1 then
              (* P <= Q となる最大の添字 *)
              upper_bound 1 j @@ fun i ->
                sum_as.(i) <= sum_as.(j) - sum_as.(i)
            else 
              (* P >= Q となる最小の添字 *)
              lower_bound 0 (j - 1) @@ fun i ->
                sum_as.(i) >= sum_as.(j) - sum_as.(i) in
          (* RとSどちらを大きくするかをb2に委ね，にぶたんする *)
          let k =
            if b2 then
              (* R <= S となる最大の添字 *)
              upper_bound (j + 1) n @@ fun k ->
                sum_as.(k) - sum_as.(j) <= sum_as.(n) - sum_as.(k)
            else 
              (* R >= S となる最小の添字 *)
              lower_bound j (n - 1) @@ fun k ->
                sum_as.(k) - sum_as.(j) >= sum_as.(n) - sum_as.(k) in
          let pqrs = [ sum_as.(i); sum_as.(j) - sum_as.(i); sum_as.(k) - sum_as.(j); sum_as.(n) - sum_as.(k) ] in
          List.fold_left max min_int pqrs - List.fold_left min max_int pqrs)) [ true; false ]) [ true; false ]
  end
  |> List.fold_left min max_int
  |> Printf.printf "%d\n"
