Bookshelf(本棚) - joi2011-day4

出典: 第10回日本情報オリンピック 日本代表選手選考会

時間制限: 1秒

メモリ制限: 64MB

20XX 年，IOI が JOI 君の住む国で開催されることになった．このニュースを聞いた JOI 君は友人に知らせるために部屋を飛び出そうとした．しかし，あまりにも急いでいたため部屋の本棚にぶつかってしまい，本は本棚から全て落ちてしまった．とにかく急いでいた JOI 君は，落ちた本を順番を全く考慮せず全て本棚に入れて家を出た．帰宅後，JOI 君は滅茶苦茶な順番に並んだ本を本来の順番に戻す作業が必要になった．

JOI 君の部屋の本棚は幅 N センチメートルであり，本棚には幅 1 センチメートルの本が N 冊入っている．本には 1 から N までの番号がふられており，本来は本棚には左から 1, …, N の順番で本が並べられていた．また，本 i の重さは A_i グラムである．

JOI 君は疲れていて本を同時にたくさん持ちたくなかったので，次のような操作を行うことで本棚を整理することにした:

本を本棚から同時に 2 冊以上取り出すことはできない．

例えば，本が左から 5, 3, 4, 1, 2 の順で並んでいるとき，本 1 を取り出し，本 4 と本 3 を順に右に動かし，
本 1 を本棚に戻すことで，本棚の本を左から 5, 1, 3, 4, 2 の順にすることができる．（下図）

[Bookshelf img1]

この操作で，JOI 君が重さ w グラムの本を本棚から取り出すとき，JOI 君はちょうど w カロリーを消費する．また，JOI 君が重さ w グラムの本を本棚に戻すときも，JOI 君はちょうど w カロリーを消費する．また，本棚はなめらかな素材でできているので，JOI 君が本棚の中で本を動かすときには JOI 君はカロリーを消費しないとしてよい．

JOI 君は疲れていたので，なるべくカロリーを消費しないようにして本棚の本を本来の順番に戻すことにした．

課題

本の数と，それぞれの本の重さ，現在の本棚の本の並び順が与えられたとき，JOI 君が本棚の本を本来の順番に並び替えるために消費するカロリーの合計の最小値を求めるプログラムを作成せよ．

制限

1 \leq N \leq 100\,000 本の数
1 \leq A_i \leq 1\,000\,000\,000 本 i の重さ (グラム)

入力

標準入力から以下の入力を読み込め．

出力

標準出力に，JOI 君が消費するカロリーの合計の最小値を表す整数を 1 行で出力せよ．

採点基準

入出力の例

入力例 出力例
4
1
6
4
3
3
4
2
1		 14

この入力例では，最初本は左から 3, 4, 2, 1 の順に並んでおり，本 1, 2, 3, 4 の重さはそれぞれ 1, 6, 4, 3 グラムである．

JOI 君は，まず以下の操作を順番に行う：

本棚の本は左から 1, 3, 4, 2 の順になる．本 1 の重さは 1 グラムなので JOI 君は 1 \times 2 = 2 カロリーを消費する．

次に，以下の操作を順番に行う：

よって JOI 君は合計 14 カロリーの消費で本を左から 1, 2, 3, 4 の順にできる．また，JOI 君が消費するカロリーをこれより少なくすることは不可能である．