macro_rules! semigroup_impl {
  ($marker:ty, $t:ty, | $lhs:pat, $rhs:pat | $append:expr) => {
    impl $crate::math::algebra::Semigroup for $marker {
      type T = $t;

      fn append($lhs: &$t, $rhs: &$t) -> $t {
        $append
      }
    }
  };
}

macro_rules! monoid_impl {
  ($marker:ty, $t:ty, | $lhs:pat, $rhs:pat | $append:expr, $identity:expr) => {
    semigroup_impl! { $marker, $t, |$lhs, $rhs| $append }

    impl $crate::math::algebra::Monoid for $marker {
      fn identity() -> $t {
        $identity
      }
    }
  };
}

macro_rules! commutative_monoid_impl {
  ($marker:ty, $t:ty, | $lhs:pat, $rhs:pat | $append:expr, $identity:expr) => {
    monoid_impl! { $marker, $t, |$lhs, $rhs| $append, $identity }

    impl $crate::math::algebra::CommutativeMonoid for $marker {}
  };
}

macro_rules! abelian_group_impl {
  ($marker:ty, $t:ty, | $lhs:pat, $rhs:pat | $append:expr, | $x:pat | $invert:expr, $identity:expr) => {
    commutative_monoid_impl! { $marker, $t, |$lhs, $rhs| $append, $identity }

    impl $crate::math::algebra::AbelianGroup for $marker {
      fn invert($x: &$t) -> $t {
        $invert
      }
    }
  };
}

fn solve<R: BufRead, W: Write>(_reader: R, _writer: &mut W) {
  let mut _scanner = Scanner::new(_reader);

  #[allow(unused_macros)]
  macro_rules! scan {
    ($t:ty) => {
      _scanner.next::<$t>().unwrap()
    };
    ($($t:ty),+) => {
      ($(scan!($t)),+)
    };
    ($t:ty; $n:expr $(; $m:expr)*) => {{
      let mut vec = Vec::with_capacity($n);
      for _ in 0..$n {
        vec.push(scan!($t $(; $m)*));
      }
      vec
    }};
    ($t_0:ty, $t_1:ty; $n:expr) => {
      scan!($t_0 = 0, $t_1 = 1; $n)
    };
    ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => {
      scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n)
    };
    ($($t:ty = $i:tt),+; $n:expr) => {{
      let mut vecs = ($(Vec::<$t>::with_capacity($n)),+);
      for _ in 0..$n {$(
        vecs.$i.push(scan!($t));
      )+}
      vecs
    }};
  }

  #[allow(unused_macros)]
  macro_rules! scan_iter {
    ($t:ty; $n:expr) => {
      _scanner.take::<$t>($n).map(|x| x.unwrap())
    };
  }

  #[allow(unused_macros)]
  macro_rules! print {
    ($fmt:expr) => {
      write!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      write!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! println {
    () => {
      writeln!(_writer).unwrap()
    };
    ($fmt:expr) => {
      writeln!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      writeln!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! eprint {
    ($fmt:expr) => {
      #[cfg(debug_assertions)]
      write!(::std::io::stderr(), $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      #[cfg(debug_assertions)]
      write!(::std::io::stderr(), $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! eprintln {
    () => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr()).unwrap()
    };
    ($fmt:expr) => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr(), $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr(), $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! dump {
    ($($x:expr),+) => {
      eprint!("[{}:{}] ", file!(), line!());
      eprintln!(concat!($(stringify!($x), " = {:?}; "),+), $($x),+);
    };
  }

  use data_structures::CumulativeSum;
  use math::algebra::AdditiveGroup;
  use std::cmp::{max, min};
  use std::iter::FromIterator;
  use std::ops::Range;

  let n = scan!(usize);
  let a = scan!(i64; n);

  let a_cumsum = CumulativeSum::<AdditiveGroup<i64>>::from_iter(a);
  let f = |range: &Range<_>, i| (a_cumsum.concat(range.start..i) - a_cumsum.concat(i..range.end)).abs();

  let search = |range: Range<_>| {
    dump!(range);
    let mut l = range.start + 1;
    let mut r = range.end - 1;
    while r - l > 2 {
      let a = (l + l + r) / 3;
      let b = (l + r + r) / 3;
      dump!(l, r, a, b, f(&range, a), f(&range, b));
      if f(&range, a) > f(&range, b) {
        l = a;
      } else {
        r = b;
      }
    }
    dump!(l, (l + r) / 2, r, f(&range, l), f(&range, (l + r) / 2), f(&range, r));
    let i = [l, (l + r) / 2, r].iter().cloned().min_by_key(|&x| f(&range, x)).unwrap();
    dump!(i);
    i
  };

  let mut ans = i64::max_value();

  let greedy_c_end = search(0..n);
  dump!(greedy_c_end);

  for c_end in 2..n - 1 {
    dump!(c_end);

    let b_end = search(0..c_end);
    let d_end = search(c_end..n);

    let b_range = 0..b_end;
    let c_range = b_end..c_end;
    let d_range = c_end..d_end;
    let e_range = d_end..n;
    dump!(b_range, c_range, d_range, e_range);

    let b_sum = a_cumsum.concat(b_range);
    let c_sum = a_cumsum.concat(c_range);
    let d_sum = a_cumsum.concat(d_range);
    let e_sum = a_cumsum.concat(e_range);
    dump!(b_sum, c_sum, d_sum, e_sum);

    let sum_min = min(b_sum, min(c_sum, min(d_sum, e_sum)));
    let sum_max = max(b_sum, max(c_sum, max(d_sum, e_sum)));
    dump!(sum_min, sum_max);

    let diff = sum_max - sum_min;
    dump!(diff);

    ans = min(ans, diff);
  }

  println!("{}", ans);
}

const STACK_SIZE_MEBIBYTES: Option<usize> = None;

fn main() {
  fn run_solver() {
    let stdin = stdin();
    let stdout = stdout();
    #[cfg(debug_assertions)]
    let mut writer = stdout.lock();
    #[cfg(not(debug_assertions))]
    let mut writer = ::std::io::BufWriter::new(stdout.lock());
    solve(stdin.lock(), &mut writer);
    writer.flush().unwrap();
  }
  if let Some(size) = STACK_SIZE_MEBIBYTES {
    let builder = ::std::thread::Builder::new().stack_size(size * 1024 * 1024);
    builder.spawn(run_solver).unwrap().join().unwrap();
  } else {
    run_solver();
  }
}

use io::Scanner;
use std::io::{stdin, stdout, BufRead, Write};

pub mod math {
  pub mod algebra {
    pub use self::abelian_group::*;
    pub use self::additive_group::*;
    pub use self::commutative_monoid::*;
    pub use self::monoid::*;
    pub use self::semigroup::*;

    mod semigroup {
      use std::fmt::Debug;

      pub trait Semigroup {
        type T: Clone + Debug;

        fn append(lhs: &Self::T, rhs: &Self::T) -> Self::T;

        fn append_assign(lhs: &mut Self::T, rhs: &Self::T) {
          *lhs = Self::append(lhs, rhs);
        }
      }
    }

    mod monoid {
      use math::algebra::Semigroup;

      pub trait Monoid: Semigroup {
        fn identity() -> Self::T;
      }
    }

    mod commutative_monoid {
      use math::algebra::Monoid;

      pub trait CommutativeMonoid: Monoid {}
    }

    mod abelian_group {
      use math::algebra::CommutativeMonoid;

      pub trait AbelianGroup: CommutativeMonoid {
        fn invert(&Self::T) -> Self::T;

        fn append_inverse(lhs: &Self::T, rhs: &Self::T) -> Self::T {
          Self::append(lhs, &Self::invert(rhs))
        }

        fn append_inverse_assign(lhs: &mut Self::T, rhs: &Self::T) {
          *lhs = Self::append_inverse(lhs, rhs);
        }
      }
    }

    mod additive_group {
      use std::marker::PhantomData;

      pub struct AdditiveGroup<T> {
        _marker: PhantomData<fn() -> T>,
      }

      macro_rules! additive_group_impl {
          ($($t:ty)+) => {$(
            abelian_group_impl! { AdditiveGroup<$t>, $t, |&lhs, &rhs| lhs + rhs, |&x| -x, 0 }
          )+};
        }

      additive_group_impl! { i32 i64 isize }
    }
  }
}

pub mod data_structures {
  pub use self::cumulative_sum::*;

  mod cumulative_sum {
    use math::algebra::{AbelianGroup, Monoid};
    use std::iter::FromIterator;
    use std::ops::{Index, IndexMut, Range, RangeTo};

    pub struct CumulativeSum<M: Monoid> {
      vec: Vec<M::T>,
    }

    impl<M: Monoid> FromIterator<M::T> for CumulativeSum<M> {
      fn from_iter<I: IntoIterator<Item = M::T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let mut vec = Vec::with_capacity(1 + iter.size_hint().0);
        vec.push(M::identity());
        for (i, x) in (1..).zip(iter) {
          vec.push(x);
          vec[i] = M::append(&vec[i - 1], &vec[i]);
        }
        vec.shrink_to_fit();
        CumulativeSum { vec: vec }
      }
    }

    impl<M: Monoid> CumulativeSum<M> {
      pub fn len(&self) -> usize {
        self.vec.len() - 1
      }

      pub fn prefix_concat(&self, range: RangeTo<usize>) -> &M::T {
        debug_assert!(range.end <= self.len());
        &self.vec[range.end]
      }
    }

    impl<G: AbelianGroup> CumulativeSum<G> {
      pub fn get(&self, index: usize) -> G::T {
        debug_assert!(index < self.len());
        self.concat(index..index + 1)
      }

      pub fn concat(&self, range: Range<usize>) -> G::T {
        assert!(range.start <= range.end);
        debug_assert!(range.end <= self.len());
        G::append_inverse(&self.vec[range.end], &self.vec[range.start])
      }
    }

    impl<M: Monoid> Index<usize> for CumulativeSum<M> {
      type Output = M::T;

      fn index(&self, index: usize) -> &M::T {
        &self.vec[index + 1]
      }
    }

    impl<M: Monoid> Index<Range<usize>> for CumulativeSum<M> {
      type Output = [M::T];

      fn index(&self, range: Range<usize>) -> &[M::T] {
        &self.vec[range.start..range.end]
      }
    }

    impl<M: Monoid> IndexMut<Range<usize>> for CumulativeSum<M> {
      fn index_mut(&mut self, range: Range<usize>) -> &mut [M::T] {
        &mut self.vec[range.start..range.end]
      }
    }
  }
}

pub mod io {
  pub use self::scanner::*;

  mod scanner {
    use std::io::BufRead;
    use std::marker::PhantomData;
    use std::str::{from_utf8, from_utf8_unchecked, FromStr};

    pub struct Scanner<R> {
      reader: R,
      buffer: Vec<u8>,
      position: usize,
    }

    impl<R: BufRead> Scanner<R> {
      pub fn new(reader: R) -> Self {
        Scanner { reader: reader, buffer: vec![], position: 0 }
      }

      pub fn next<T: Parse>(&mut self) -> Option<T> {
        Parse::parse(self.next_bytes().unwrap_or(&[]))
      }

      pub fn take<T: Parse>(&mut self, n: usize) -> Take<R, T> {
        Take { scanner: self, n: n, _marker: PhantomData }
      }

      pub fn next_bytes(&mut self) -> Option<&[u8]> {
        if self.buffer.is_empty() {
          self.read_line();
        }
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') => self.position += 1,
            Some(&b'\n') => self.read_line(),
            Some(_) => break,
            None => return None,
          }
        }
        let start = self.position;
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') | Some(&b'\n') | None => break,
            Some(_) => self.position += 1,
          }
        }
        Some(&self.buffer[start..self.position])
      }

      fn read_line(&mut self) {
        self.position = 0;
        self.buffer.clear();
        self.reader.read_until(b'\n', &mut self.buffer).unwrap();
      }
    }

    pub struct Take<'a, R: 'a, T> {
      scanner: &'a mut Scanner<R>,
      n: usize,
      _marker: PhantomData<fn() -> T>,
    }

    impl<'a, R: BufRead, T: Parse> Iterator for Take<'a, R, T> {
      type Item = Option<T>;

      fn next(&mut self) -> Option<Self::Item> {
        if self.n > 0 {
          self.n -= 1;
          Some(self.scanner.next())
        } else {
          None
        }
      }

      fn size_hint(&self) -> (usize, Option<usize>) {
        (self.n, Some(self.n))
      }
    }

    impl<'a, R: BufRead, T: Parse> ExactSizeIterator for Take<'a, R, T> {}

    pub trait Parse: Sized {
      fn parse(bytes: &[u8]) -> Option<Self>;
    }

    impl Parse for u8 {
      fn parse(bytes: &[u8]) -> Option<Self> {
        if bytes.len() == 1 {
          Some(*unsafe { bytes.get_unchecked(0) })
        } else {
          None
        }
      }
    }

    macro_rules! parse_impl {
      ($($t:ty)+) => {$(
        impl Parse for $t {
          fn parse(bytes: &[u8]) -> Option<Self> {
            let s = if cfg!(debug_assertions) { from_utf8(bytes).unwrap() } else { unsafe { from_utf8_unchecked(bytes) } };
            <$t>::from_str(s).ok()
          }
        }
      )+};
    }

    parse_impl! { i32 i64 isize u32 u64 usize String }
  }
}


Measured memory_bytes: 10492