{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE BinaryLiterals             #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveFunctor              #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE DerivingVia                #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE KindSignatures             #-}
{-# LANGUAGE LambdaCase                 #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE MultiWayIf                 #-}
{-# LANGUAGE NumericUnderscores         #-}
{-# LANGUAGE OverloadedStrings          #-}
{-# LANGUAGE PatternSynonyms            #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE RecordWildCards            #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TupleSections              #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeInType                 #-}
{-# LANGUAGE UnboxedTuples              #-}
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
{- base -}
import           Control.Applicative
import qualified Control.Arrow                     as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import qualified Data.Char                         as Char
import           Data.Complex
import qualified Data.Foldable                     as Foldable
import           Data.Function
import qualified Data.List                         as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ord
import           Data.Ratio
import           Data.Semigroup
import qualified Data.Word                         as Word
import           Foreign                           hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                     as ArrIO
import qualified Data.Array.MArray                 as ArrMA
import qualified Data.Array.ST                     as ArrST
import qualified Data.Array.Storable               as ArrStore
import qualified Data.Array.Unboxed                as ArrU
{- bytestring -}
import qualified Data.ByteString                   as BS
import qualified Data.ByteString.Builder           as BSB
import qualified Data.ByteString.Builder.Extra     as BSBE
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.ByteString.Lazy              as BSL
import qualified Data.ByteString.Lazy.Builder      as BSLB
import qualified Data.ByteString.Lazy.Char8        as BSLC8
import qualified Data.ByteString.Unsafe            as BSU
{- containers -}
import qualified Data.Graph                        as Graph
import           Data.IntMap                       (IntMap)
import qualified Data.IntMap                       as IntMap
import           Data.IntSet                       (IntSet)
import qualified Data.IntSet                       as IntSet
import qualified Data.Sequence                     as Seq
import qualified Data.Tree                         as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- time -}
import qualified Data.Time.Calendar                as Calender
import qualified Data.Time.Calendar.Easter         as CalenderE
import qualified Data.Time.Calendar.Julian         as CalenderJ
import qualified Data.Time.Calendar.MonthDay       as CalenderM
import qualified Data.Time.Calendar.OrdinalDate    as CalenderD
import qualified Data.Time.Calendar.WeekDate       as CalenderW
import qualified Data.Time.LocalTime               as LocalTime
{- transformers -}
import qualified Control.Monad.Trans.Accum         as TAccum
import qualified Control.Monad.Trans.Cont          as TCont
import qualified Control.Monad.Trans.Identity      as TId
import qualified Control.Monad.Trans.Reader        as TReader
import qualified Control.Monad.Trans.State.Lazy    as TStateL
import qualified Control.Monad.Trans.State.Strict  as TStateS
import qualified Control.Monad.Trans.Writer.CPS    as TWriteC
import qualified Control.Monad.Trans.Writer.Lazy   as TWriteL
import qualified Control.Monad.Trans.Writer.Strict as TWriteS
{- vector -}
import qualified Data.Vector                       as V
import qualified Data.Vector.Generic               as VG
import qualified Data.Vector.Generic.Mutable       as VGM
import qualified Data.Vector.Mutable               as VM
import qualified Data.Vector.Primitive             as VP
import qualified Data.Vector.Primitive.Mutable     as VPM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
main :: IO ()
main = do
  m <- parse1
  v <- parseM m
  print $ solver v (m - 1)

solver :: VU.Vector Int -> Int -> Int
solver xs = dyna phi psi
  where
    psi 0 = NELF (xs VU.! 0) Nothing
    psi i = NELF (xs VU.! i) (Just (i - 1))

    phi (NELF j Nothing) = j
    phi (NELF j (Just t)) = max f1 f2
      where
        f1 = extract t
        f2 = case sub t of
          NELF _ Nothing -> j
          NELF _ (Just t') -> extract t' + j 
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
  return $ VU.unzip vectup
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
  return $ VU.unzip3 vectup
-------------------------------------------------------------------------------
data NELF a = NELF Int (Maybe a)
  deriving (Functor)
newtype Fix f = InF { outF :: f (Fix f) }
pair :: (a -> b, a -> c) -> a -> (b, c)
pair (f, g) x = (f x, g x)
cata :: Functor f => (f a -> a) -> (Fix f -> a)
cata phi = phi . fmap (cata phi) . outF
ana :: Functor f => (a -> f a) -> (a -> Fix f)
ana psi = InF . fmap (ana psi) . psi
hylo :: Functor f => (f a -> a) -> (b -> f b) -> (b -> a)
hylo phi psi = phi . fmap (hylo phi psi) . psi -- cata phi . ana psi
meta :: (Functor f, Functor g) => (f a -> a) -> (a -> b) -> (b -> g b) -> (Fix f -> Fix g)
meta phi chi psi = ana psi . chi . cata phi
prepro :: Functor f => (forall a. f a -> f a) -> (f a -> a) -> (Fix f -> a)
prepro chi phi = phi . fmap (prepro chi phi . cata (InF . chi)) . outF
postpro :: Functor f => (forall a. f a -> f a) -> (a -> f a) -> (a -> Fix f)
postpro chi psi = InF . fmap (ana (chi . outF) . postpro chi psi) . psi
para :: Functor f => (f (Fix f, a) -> a) -> (Fix f -> a)
para phi = phi . fmap ((,) <*> para phi) . outF
apo :: Functor f => (a -> f (Either (Fix f) a)) -> (a -> Fix f)
apo psi = InF . fmap (uncurry either (id, apo psi)) . psi
zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> (Fix f -> a)
zygo phi phi' = snd . cata (pair (phi . fmap fst, phi'))
cozygo :: Functor f => (a -> f a) -> (b -> f (Either a b)) -> (b -> Fix f)
cozygo psi psi' = ana (uncurry either (fmap Left . psi, psi')) . Right
mutu :: Functor f => (a -> b) -> (f a -> a) -> (Fix f -> b)
mutu chi phi = chi . cata phi
comutu :: Functor f => (b -> a) -> (a -> f a) -> (b -> Fix f)
comutu chi psi = ana psi . chi
data Fx f a x =  Fx { unFx :: Either a (f x) }
data Hx f a x =  Hx { unHx :: (a, f x) }
instance Functor f => Functor (Fx f a) where
  fmap f (Fx (Left x))  = Fx (Left x)
  fmap f (Fx (Right x)) = Fx (Right (fmap f x))
instance Functor f => Functor (Hx f a) where
  fmap f (Hx (x, y)) = Hx (x, fmap f y)
newtype Free f a = Free { unFree :: Fix (Fx f a) }
newtype CoFree f a = CoFree { unCoFree :: Fix (Hx f a) }
instance Functor f => Functor (Free f) where
  fmap f = Free . cata (InF . phi) . unFree
    where
      phi (Fx (Left a))  = Fx (Left (f a))
      phi (Fx (Right b)) = Fx (Right b)
instance Functor f => Functor (CoFree f) where
  fmap f = CoFree . ana (psi . outF) . unCoFree
    where
      psi (Hx (a, x)) = Hx (f a, x)
extract :: Functor f => CoFree f t -> t
extract cf = case outF (unCoFree cf) of
  Hx (a, _) -> a
sub :: Functor f => CoFree f a -> f (CoFree f a)
sub cf = case outF (unCoFree cf) of
  Hx (_, b) -> fmap CoFree b
inject :: Functor f => a -> Free f a
inject = Free . InF . Fx . Left
histo :: Functor f => (f (CoFree f t) -> t) -> (Fix f -> t)
histo phi = extract . cata (CoFree . InF . fmap unCoFree . Hx . pair (phi, id))
futu :: Functor f => (t -> f (Free f t)) -> (t -> Fix f)
futu psi = ana (uncurry either (psi, id) . unFx . fmap Free . outF . unFree) . inject
chrono :: Functor f => (f (CoFree f b) -> b) -> (a -> f (Free f a)) -> (a -> b)
chrono phi psi = extract . hylo phi' psi' . inject
  where
    phi' = CoFree . InF . fmap unCoFree . Hx . pair (phi, id)
    psi' = uncurry either (psi, id) . unFx . fmap Free . outF . unFree
cochrono :: Functor f => (f (CoFree f t) -> t) -> (t -> f (Free f t)) -> (Fix f -> Fix f)
cochrono phi psi = futu psi . histo phi
dyna :: Functor f => (f (CoFree f b) -> b) -> (a -> f a) -> (a -> b)
dyna phi psi = chrono phi (fmap inject . psi)
codyna :: Functor f => (f b -> b) -> (a -> f (Free f a)) -> (a -> b)
codyna phi psi = cata phi . futu psi
exo :: Functor h => (m b -> b, b -> n b) -> (h b -> m b) -> (h a -> h (g a)) -> (f a -> a, g a -> h a) -> (g a -> b)
exo c f g d = hylo (fst c . f) (g . snd d)
mcata :: (forall b. (b -> a) -> f b -> a) -> (Fix f -> a)
mcata phi = phi (mcata phi) . outF
mana :: (forall b. (a -> b) -> a -> f b) -> (a -> Fix f)
mana psi = InF . psi (mana psi)
mhisto :: (forall b. (b -> a) -> (b -> f b) -> f b -> a) -> (Fix f -> a)
mhisto psi = psi (mhisto psi) outF . outF
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------