import Data.List
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
import Data.Vector.Unboxed as V (drop,take,sum,last,(!),fromList,Vector)
import Control.Monad
import Control.Monad.ST

type DP s = STUArray s (Int,Int) Int

dp_i :: DP s -> Vector Int -> Int -> Int  -> ST s ()
dp_i dparr as i j = do
  sums <- forM [i..j-1] $ \k -> do
    l <- readArray dparr (i,k)
    r <- readArray dparr (k+1,j)
    return $ l+r
  writeArray dparr (i,j) $ (minimum sums) + (V.sum $ V.take (j-i+1) $ V.drop (i-1) as)

solve :: Vector Int -> Int -> ST s Int
solve as n = do
  dparr <- newArray ((1,1),(n,n)) 0
  forM_ [1..n-1] $ \diff ->
    forM_ [1..n-diff] $ \i -> dp_i dparr as i (diff+i)
  readArray dparr (1,n)

main :: IO ()
main = do
  n <- read<$> getLine
  as <- map read.words <$> getLine
  print $ runST $ solve (V.fromList as) n