
let () =
  Scanf.scanf "%d" @@ fun n ->
  let a = Array.init n (fun _ -> Scanf.scanf " %d" ((+) 0)) in
  for i = 1 to n-1 do a.(i) <- a.(i) + a.(i-1) done;

  let psum l r =
    if l >= r then 0
    else if l = 0 then a.(r-1) else a.(r-1) - a.(l-1)
  in
  let adj l r m =
    if psum l m - psum m r <= psum (m-1) r - psum l (m-1) then m else m-1
  in
  let rec upd l r m =
    if r <= m then adj l r m
    else
      if psum l m >= psum m r then adj l r m
      else upd l r (m+1)
  in

  let rec loop i v m1 m2 =
    if i > n-2 then v
    else
      let m1' = upd 0 i m1 in
      let m2' = upd i n m2 in

      let p, q, r, s = psum 0 m1', psum m1' i, psum i m2', psum m2' n in
      let v' = List.(fold_left max p [p;q;r;s] - fold_left min p [p;q;r;s]) in

      loop (i+1) (min v v') m1' m2'
  in
  loop 2 a.(n-1) 1 3 |> Printf.printf "%d\n"
