C - Pretty Derby


配点 :
  

問題文


あなたはトレセン学園に所属する優秀なトレーナーであり、担当のウマ娘の育成に勤しんでいます。
これから 回のレースが開催され、 回目のレースに出場したウマ娘が新しく獲得できるファンの数は 人です。
あなたの仕事は、担当のウマ娘の出場するレースを適切に決めることによって、彼女が獲得するファンの数を最大化することです。
ただし、彼女が疲れてしまうので、 回以上連続でレースに出場させることは出来ません。
適切に出場するレースを決めたとき、彼女が獲得できるファンの人数の最大値を求めてください。

  

制約


  • 入力は全て整数

  

入力


入力は以下の形式で標準入力から与えられます。


  

出力


答えを出力してください。

  

入力例1


5
5 2 4 9 1

出力例1


18

回目のレースに出場させるのが良いです。獲得できるファンの数は 人となり、これが最適です。
例えば 回目のレースに出場させると 人のファンが獲得できますが、 回目のレースで 回連続で出場してしまっているため、このような出場するレースの決め方は出来ないことに注意してください。
 

入力例2


1
100000

出力例2


100000

回しかレースが開催されないので、そのレースにそのまま出場させれば良いです。  
 

入力例3


10
100 100 100 100 100 100 100 100 100 100

出力例3


700

提出


Go (1.14)