import Data.List

type Index = Int

data Memo = Memo { p :: Integer, j :: Index, total :: Integer } deriving (Show, Eq, Ord)
data State = State { z :: Integer, mins :: [Memo], i :: Index } deriving Show

e = 1000000000

binsearch' :: [Memo] -> Integer -> Int -> Index -> Index -> Memo
binsearch' l x n low high
  | n == 0 = l !! low
  | x < p memo = binsearch' l x (n-1) low mid
  | otherwise = binsearch' l x (n-1) mid high
  where
    mid = (low + high) `div` 2
    memo = l !! mid

binsearch :: [Memo] -> Integer -> Memo
binsearch l x = binsearch' l x 20 0 (length l)

getLower :: Index -> [Memo] -> [Memo]
getLower i = filter $ \x -> j x <= i

step :: State -> Integer -> State
step state x = State z' mins' $ i+1
  where
    State z mins i = state
    Memo p j total = binsearch mins x
    a = total + (x * fromIntegral (i - j))
    z' = z + a
    memo' = Memo x i a
    mins' = insert memo' $ getLower j mins

solve :: [Integer] -> Integer
solve l = z result
  where
    memo = Memo 0 0 0
    state = State 0 [memo] 1
    result = foldl' step state $ reverse l

main = getContents >>= print.solve.map read.words.last.lines
