問題文

N 人のパ研部員が左右一列に並んでいます。左から i 番目のパ研部員の身長は A_i です。

あなたの仕事は、以下の操作を 0 回以上繰り返してパ研部員たちが背の順で並んでいる、即ち任意の i\ (1\leq i\leq (列にいる部員の数)-1) に対して (左から i 番目にいる部員の身長)<(左から i+1 番目にいる部員の身長) が成り立つようにすることです。

• 今列にいるパ研部員の数を M として、整数 l,\ r\ (1\leq l\leq r\leq M) を選ぶ。選んだ時点で左から l 番目にいる部員の身長を L、r 番目にいる部員の身長を R としたとき、コスト L+R を払って 左から l,\ l+1,\ldots,\ r 番目のパ研部員を列から取り除く。

あなたは仕事を達成するために、最小で合計いくらのコストを払う必要がありますか？

列に誰もいない状態も背の順で並んでいると見なし、また、操作を繰り返す間部員の身長は変化しません。

入力例1

4
3 4 1 2

出力例1

3

入力例2

6
1 2 3 4 5 6

出力例2

0

入力例3

7
1 5 4 7 2 3 6

出力例3

3