{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE Strict #-}
{-# LANGUAGE StrictData #-}
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector.Algorithms.Insertion as VA
import Data.Array.Unboxed
import Data.Array.ST
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Control.Monad.ST
import Data.List
import Data.Char

dp :: Int -> VU.Vector (Int,Int) -> UArray (Int,Int) Int
dp n bs = runSTUArray $ do
    arr <- newArray ((0,0),(n,n)) 0
    forM_ [0..n-1] $ \i -> do
        forM_ [0..n-i-1] $ \j -> do
            ij <- readArray arr (i,j)
            let (index,value) = bs VU.! (i+j)
                left          = ij + value*(abs (index-i))
                right         = ij + value*(abs ((n-j-1)-index))
            l <- readArray arr (i+1,j)
            writeArray arr (i+1,j) $ max l left
            r <- readArray arr (i,j+1)
            writeArray arr (i,j+1) $ max r right
    return arr
            
            
            

main :: IO ()
main = do
    n <- readLn
    as <- VU.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    let bs :: VU.Vector (Int,Int)
        bs = runST $ do
        bs <- VU.thaw (VU.indexed as)
        VA.sortBy (\j k -> compare (snd k) (snd j)) bs
        VU.freeze bs
    print $ maximum [ dp n bs ! (i,n-i) | i <- [0..n]]  