AT_past202306_k 入れ替えてソート

$ (1,2,\ldots,N) $ の並び替えである長さ $ N $ の数列 $ P=(P_1,P_2,\ldots,P_N) $ があります。 あなたはこの数列に対して、以下の操作を $ 0 $ 回以上の好きな回数だけ行うことができます。 - $ 1 $ 以上 $ N-1 $ 以下の整数 $ i $ を選び、 $ P $ の $ i $ 番目の要素と $ i+1 $ 番目の要素を入れ替える。この操作には、入れ替える $ 2 $ 数の和に等しいコストがかかる。 $ P $ を昇順にソートするために必要な最小コストを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

答えを出力せよ。

### Sample Explanation 1 例えば次のように $ 3 $ 回の操作を行うことで $ P $ を昇順にソートすることができます。 - $ i=1 $ と選び、 $ 3 $ と $ 2 $ を入れ替える。 $ 5 $ のコストがかかり、数列は $ (2,3,1,4) $ になる。 - $ i=2 $ と選び、 $ 3 $ と $ 1 $ を入れ替える。 $ 4 $ のコストがかかり、数列は $ (2,1,3,4) $ になる。 - $ i=1 $ と選び、 $ 2 $ と $ 1 $ を入れ替える。 $ 3 $ のコストがかかり、数列は $ (1,2,3,4) $ になる。 コスト $ 12 $ 未満で数列を昇順にソートすることはできないため、答えは $ 12 $ になります。 ### Sample Explanation 3 操作をする必要がないこともあります。 ### Constraints - $ 1 \leq N \leq 2\times 10^5 $ - $ N $ は整数である - $ P $ は $ (1,2,\ldots,N) $ を並び替えた数列である