12571257 SUSTech Online Judge
Problem 1257 --Vinceblack's store

1257: Vinceblack's store

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1152  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]