/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
(1,2,\ldots,N) の並び替えである長さ N の数列 P=(P_1,P_2,\ldots,P_N) があります。
あなたはこの数列に対して、以下の操作を 0 回以上の好きな回数だけ行うことができます。
- 1 以上 N-1 以下の整数 i を選び、P の i 番目の要素と i+1 番目の要素を入れ替える。この操作には、入れ替える 2 数の和に等しいコストがかかる。
P を昇順にソートするために必要な最小コストを求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- N は整数である
- P は (1,2,\ldots,N) を並び替えた数列である
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 3 2 1 4
出力例 1
12
例えば次のように 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 になります。
入力例 2
9 3 1 4 5 9 2 6 8 7
出力例 2
96
入力例 3
6 1 2 3 4 5 6
出力例 3
0
操作をする必要がないこともあります。
Problem Statement
There is a sequence of length N, P=(P_1,P_2,\ldots,P_N), which is a permutation of (1,2,\ldots,N).
You can perform the following operation on this sequence any number of times, possibly zero:
- Choose an integer i between 1 and N-1, inclusive, and swap the i-th element and the (i+1)-th element of P. The cost of this operation is the sum of the two numbers being swapped.
Find the minimum cost required to sort P in ascending order.
Constraints
- 1 \leq N \leq 2\times 10^5
- N is an integer.
- P is a permutation of (1,2,\ldots,N).
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 3 2 1 4
Sample Output 1
12
For example, you can sort P in ascending order by performing the following three operations:
- Choose i=1 to swap 3 and 2. This costs 5, and the sequence becomes (2,3,1,4).
- Choose i=2 to swap 3 and 1. This costs 4, and the sequence becomes (2,1,3,4).
- Choose i=1 to swap 2 and 1. This costs 3, and the sequence becomes (1,2,3,4).
Since it is impossible to sort the sequence in ascending order with a cost less than 12, the answer is 12.
Sample Input 2
9 3 1 4 5 9 2 6 8 7
Sample Output 2
96
Sample Input 3
6 1 2 3 4 5 6
Sample Output 3
0
Sometimes, no operations are needed.