{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}

import Control.Monad
import Control.Monad.ST
import Data.Int
import Data.List
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.ByteString.Char8 as B

main=do
  n<-readLn::IO Int
  as<-unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine::IO[Int]
  --
  let !cs = f n as
  --
  let fl = fi cs 1 2
  let fr = fi cs 3 n
  let s1 = sss cs n 1 2 3
  print.minimum.map(\(a,_,_)->a) $ scanl (\(s,fl,fr) i->sol cs n i fl fr) (s1,fl,fr) [3..n-2]
--
f n as = V.create $ do
  v<-MV.replicate (n+1) 0 :: ST s (MV.STVector s Int)
  forM_ (zip as [1..]) $ \(a,i) ->
    MV.unsafeRead v (i-1) >>= MV.unsafeWrite v i.(a+)
  return v

ss cs s e = cs V.! e - cs V.! (s-1)

sol cs n i fl fr = (sb, fl', fr')
  where
    sb = sss cs n fl' i fr'
    fl' = fi' cs 1 i (fl-1) (maxBound::Int)
    fr' = fi' cs (i+1) n (fr-1) (maxBound::Int)

sss cs n a b c = maximum sl - minimum sl
  where
    sl = [s1,s2,s3,s4]
    s1 = ss cs 1 a
    s2 = ss cs (a+1) b
    s3 = ss cs (b+1) c
    s4 = ss cs (c+1) n

fi cs s e = fi' cs s e s (maxBound::Int)
fi' cs s e i pd
  | pd < pc = i-1
  | i == e = i-1
  | i > e = undefined
  | True = fi' cs s e (i+1) pc
  where
    pc = abs (ri-li)
    li = ss cs s i
    ri = ss cs (i+1) e
