Submit: 1153 Solved: 219

[Submit][Status][Web Board]

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.

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.

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 one integer indicates the minimum cost.

```
3
2 3 1
```

`7`

2 3 1 -> 2 1 3 cost: 4

2 1 3 -> 1 2 3 cost: 3

total cost: 4+3=7