/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
Indeed 社の N 人の社員が左から右に向かって一列に並んでいます。 各社員には身長が定まっており、自分より左に並んでいる全ての社員よりも身長が高い場合に限り、列の左側から見たときに顔が見えます。
社員達は既に並んでいますが、左右に隣接する 2 人の社員どうしは、それらの位置を入れ替わるという行動を自由な順番で何度でも行うことができます。 位置を入れ替わるときは、2 者の身長が低い方の身長の値だけのコストがかかります。
合計コストは各入れ替わりにかかるコストの総和として定義されます。
今、A さんは、列の左側から見たときに N 人の社員全員の顔が見えるように並んで欲しいと思っており、それを達成するように並んだときにのみ A さんは満足します。
あなたの仕事は、列における社員の身長が与えられるので、A さんが満足するために必要な最小の合計コストを答えることです。 ただし、どのように並んでも A さんが満足しない場合もあります。その場合はその旨を報告してください。
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 … H_N
- 1 行目には、並んでいる社員の人数を表す整数 N (1≦N≦10^5) が与えられる。
- 2 行目には、列に並んでいる社員の身長を表す N 個の整数が空白区切りで与えられる。そのうち i(1≦i≦N) 番目には、列において左から i 番目の位置にいる社員の身長を表す整数 H_i (1≦H_i≦10^8) が与えられる。
部分点
この問題には部分点が設定されている。
- 1≦N≦1000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
- 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。
出力
1 行目に、A さんが満足するために必要な最小の合計コストを出力せよ。ただし、どのように並んでも A さんが満足しない場合は -1 を出力せよ。出力の末尾に改行を入れること。
入力例1
4 4 1 3 2
出力例1
8
左から順番に身長が 1,2,3,4 となるように並ぶことで、列の左側から見たときに全員の顔を見ることができ、A さんは満足します。 この並びを達成するために必要な最小の合計コストは 8 で、以下のように入れ替わることによって達成できます。
- 最初に、身長 4 の人と 身長 1 の人が入れ替わります。この行動にかかるコストは 1 で、直後の並びは 1,4,3,2 です。
- 次に、身長 4 の人と 身長 3 の人が入れ替わります。この行動にかかるコストは 3 で、直後の並びは 1,3,4,2 です。
- 次に、身長 4 の人と 身長 2 の人が入れ替わります。この行動にかかるコストは 2 で、直後の並びは 1,3,2,4 です。
- 最後に、身長 3 の人と 身長 2 の人が入れ替わります。この行動にかかるコストは 2 で、直後の並びは 1,2,3,4 です。
入力例2
5 1 1 2 2 3
出力例2
-1
どのように並んだとしても、同じ身長の人同士の顔を同時に見ることはできません。したがって -1 を出力しなければなりません。