Problem 1257 --Vinceblack's store1257: Vinceblack's store
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1153 Solved: 219
[Submit][Status][Web Board]Description
Vinceblack has a candy store with \(n\) candies in a row, and the volume of each candy is \(v_i\). To make the candy store more beautiful, Vince wants to move some candies to make them sorted in increasing order in volume. However, he can only exchange two adjacent candies, and the cost of the movement equals to the sum of volumes. Now Vince wants you to tell him what is the minimum cost to sort the candies.
Input
The first line of the input contains one integer \(n(1\le n\le 100\ 000)\).
The second line contains \(n\) integers \(v_{1},v_{2},...,v_{n}(1\le v_{i}\le 100\ 000\ 000)\).
It is guaranteed that the volume of all the candies are distinct.
Output
Output one integer indicates the minimum cost.
Sample Input
3
2 3 1
Sample Output
7
HINT
2 3 1 -> 2 1 3 cost: 4
2 1 3 -> 1 2 3 cost: 3
total cost: 4+3=7
Source
[Submit][Status]