時間制限 : sec, メモリ制限 : KB
English / Japanese  
この問題は難易度の高い応用問題です。

Minimum Cost Sort

重さ $w_i (i = 0, 1, ..., n-1)$ の $n$ 個の荷物が1列に並んでいます。これらの荷物をロボットアームを用いて並べ替えます。1度の操作でロボットアームは荷物 $i$ と荷物 $j$ を持ち上げ、それらの位置を交換することができますが、$w_i + w_j$ のコストがかかります。ロボットアームは何度でも操作することができます。

与えられた荷物の列を重さの昇順に整列するコストの総和の最小値を求めてください。

入力

1行目に整数 $n$ が与えられます。2行目に $n$ 個の整数 $w_i (i = 0, 1, 2, ... n-1)$ が空白区切りで与えられます。

出力

最小値を1行に出力してください。

制約

  • $1 \leq n \leq 1,000$
  • $0 \leq w_i\leq 10^4$
  • $w_i$ は全て異なる値

入力例 1

5
1 5 3 4 2

出力例 1

7

入力例 2

4
4 3 2 1

出力例 2

10