{-# 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 ((!))


binSearch :: V.Vector Int -> Int -> Int
binSearch vect goal = loop 0 vect
  where
    loop j vec | len <= 1  = j
               | odd len   = if goal <= vec!mid
                             then loop j       (V.slice 0   (mid+1) vec)
                             else loop (j+mid) (V.slice mid (mid+1) vec)
               | otherwise = if goal <= avgmid
                             then loop j       (V.slice 0    mid    vec)
                             else loop (j+mid) (V.slice mid  mid    vec)
      where
        len = V.length vec
        mid = len `shiftR` 1
        avgmid = (vec!(mid-1) + vec!mid) `shiftR` 1
                                 
query :: Int -> V.Vector Int -> Int
query n sums =
  minimum
  $ map (uncurry subtract . minMax . map diff . pair)
  $ scanl' findMids (0,0,binSearch sums (sums ! n `shiftR` 1)) [1..n]
  where
    findMids (!i,_,!k) !j
      = (i + binSearch (V.slice i  (j-i+1)  sums) (sums!j `shiftR` 1), j,
         k' + binSearch (V.slice k' (n-k'+1) sums)
          ((sums!n + sums!j) `shiftR` 1))
      where k' = k `max` j
    pair (i,j,k) =  [(0,i),(i,j),(j,k),(k,n)]
    diff (i,j) = sums!j - sums!i
    minMax = foldl' (\(mn,mx) v -> (mn `min` v, mx `max` v)) (maxBound,0) 
     
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
