ごみ圧縮

ミハエル・エンダーの小説「母」に登場する清掃員のベポおじいさんは毎日道でゴミを拾い、拾ったゴミをゴミ箱に入れた.彼は無限のゴミ箱を持っていて、これらのゴミ箱は少し特別です.一般的なゴミ箱とは異なり、このゴミ箱は自動的に含まれるごみを圧縮し、これまでに含まれていたごみの中で、現在入っているごみよりも軽量なごみが圧縮されます.たとえば、

上図のように、3、4、6重のゴミが入ったゴミ箱に5重のゴミを入れると、5より軽い3、4が自動的に圧縮されて消えてしまいます.もちろん、ゴミ箱が無限にあるので、いつでも新しいゴミ箱にゴミを入れることができます.ただし、ゴミは拾う順番で処理します.ごみの順番を変えたいなら、灰色の紳士がベポおじいさんの時間を盗むことになります(👻).
貝波おじいさんはごみを全部掃除して、ゴミ箱からごみを出して、積み上げて重さを測りました.ゴミを掃除するとき、ゴミの入れ方によって、可能な重さはいろいろありますが、貝波おじいさんは達人なので、いつも最終的な重さを最小限に抑えています.
ごみの重量情報は,入力されたN個の要素(Nは百万以下の自然数,各要素の自然数は百万以下)に配列される.ごみがインデックスを並べた速い順序で処理される場合は、貝波おじいさんが確認した最終重量値を出力してください.(制限時間:1秒)
例1)

[6,4,3,5]

出力:11
例2)

[4,3,1,2]

出力:9
*振り返る:トイレでゴミ箱を掃除しているおばさんを見て、思い出した質問.筋の構造がこじつけである.しかも思ったより積み上げやすい.後で別の条件をつけよう.