import qualified Data.ByteString.Char8 as C
import Data.Int
import qualified Data.IntMap.Strict as M
import Data.List

main = C.interact $ C.pack . show . sol . get

get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . C.lines

sol ::[[Int]] -> Int64
sol [[n],as] = maximum $ zipWith (+) lsum rsum
  where
  lsum = fmap snd $ scanl' f (sl,xl) am
  rsum = fmap snd $ scanr (flip f) (sr,xr) (negate <$> am)
  (al:am:ar:_) = unfoldr (\xs -> if null xs then Nothing else Just (splitAt n xs)) as
  ar' = negate <$> ar
  sl = M.fromListWith (+) $ zip al (repeat 1)
  sr = M.fromListWith (+) $ zip ar' (repeat 1)
  xl = foldl' nsum (0 :: Int64) al
  xr = foldl' nsum (0 :: Int64) ar'

nsum s k = s + fromIntegral k

f (s,x) a = if a>k then (delins a k s, x+fromIntegral (a-k)) else (s,x)
  where k = fst $ M.findMin s

delins a k = M.insertWith (+) a 1 . 
  M.update (\c -> if c==1 then Nothing else Just (c-1)) k