{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Control.Applicative
import Data.List
import Data.Maybe
import Data.Bits
import qualified Data.IntMap.Strict as M
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed ((!))


findMidWithin :: V.Vector Int -> (Int,Int) -> Int
findMidWithin vec (from,to) =
    fromMaybe to $ testIndex
    <$> V.findIndex ((>= lohi) . (`shiftL` 1)) (V.slice from (to-from+1) vec)
    where
      len = V.length vec
      n = len - 1
      lohi = vec!0 + vec!n
      testIndex 0 = from
      testIndex j | lohi <= vec!(from+j-1) + vec!(from+j) = from+j-1
                  | otherwise                             = from+j

findMidIntvWithin :: V.Vector Int -> (Int,Int) -> (Int,Int) -> Int
findMidIntvWithin vec (intvFrom,intvTo) (withinFrom,withinTo)
  = intvFrom
    + findMidWithin (V.slice intvFrom (intvTo-intvFrom+1) vec)
       (withinFrom - intvFrom, withinTo - intvFrom)
                                 
query :: Int -> V.Vector Int -> Int
query n sums =
  V.minimum $ V.imap (curry $ uncurry (-) . maxmin . map diff . poss) inds
  where
    maxmin = foldl' (\(mx,mn) v -> (mx `max` v, mn `min` v))
                    (minBound,maxBound)
    diff (i,j) = sums!j - sums!i
    poss (j',(i,k)) = [(0,i),(i,j),(j,k),(k,n)]
      where j = j' + 2
    inds =
      V.unfoldrN (n-3)
                 (\(!i,!j,!k) ->
                    let j' = findMidIntvWithin sums (0,i) (j,i-1)
                        k' = findMidIntvWithin sums (i,n) (k,n-1)
                    in Just ((j',k'),(i+1,j',k'`max`(i+1))))
                 (2,1,3)
     
main :: IO ()
main = do
  n <- read <$> getLine
  ais <- V.unfoldrN n (B.readInt . B.dropWhile (==' ')) <$> B.getLine
  putStrLn $ show $ query n $ V.scanl (+) 0 ais
