import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (sortBy)
import Data.Function (on)
import qualified Data.Vector.Unboxed as VU

main :: IO ()
main = do
  n <- unsafeTextToInt <$> T.getLine :: IO Int
  let
    f :: [(Int, Int)] -> Int
    f = VU.maximum . foldl step (VU.singleton 0)
      where
        step :: VU.Vector Int -> (Int, Int) -> VU.Vector Int
        step v (x, i) = VU.generate (succ l) step'
          where
            l :: Int
            l = VU.length v
            step' :: Int -> Int
            step' 0             = VU.head v + x * (i - l)
            step' j | j < l     = max (v VU.! pred j + x * (n - pred j - i)) (v VU.! j + x * (i - (l - j)))
                    | otherwise = VU.last v + x * (n - pred l - i)
  as <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    ais :: [(Int, Int)]
    ais = sortBy (flip compare `on` fst) . flip zip [1..] $ as
  print . f $ ais

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
