import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    as <- getIntList
    let ais = reverse . sort $ zip as [1..]
    print $ solve [1..n] [n,n-1..1] ais

solve _ _ [] = 0
solve (s:ss) _ ((a,i):[]) = abs (s-i) * a
solve (s:ss) (l:ls) ((a,i) : (b,j) : ais)
    | m == a' = solve' (s:ss) (l:ls) ((a,i) : (b,j) : ais)
    | m == b' = solve' (s:ss) (l:ls) ((b,j) : (a,i) : ais)
  where a' = max (abs (s-i)) (abs (l-i))
        b' = max (abs (s-j)) (abs (l-j))
        m = max a' b'

solve' _ _ [] = 0
solve' (s:ss) (l:ls) ((a,i):ais)
    | si < li = (li * a) + solve (s:ss) ls ais
    | si > li = (si * a) + solve ss (l:ls) ais
    | si == li = si * a + max (solve ss (l:ls) ais) (solve (s:ss) ls ais)  
  where si = abs (s-i)
        li = abs (l-i)