House Moving

Interview

Time limit3sMemory limit512 MB

Summary

Given a permutation of weights, move pieces to any position at cost equal to the piece's weight so the final order is sorted; minimize total cost.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Array, Greedy
Solved: No attempts yet

Problem

Taro is moving to a new house. He has a lot of luggage, so he decided to hire a moving company to carry it. Since the pieces have various weights, he asked the movers to place them in order from lightest to heaviest so they would be easy to identify, but the movers placed the luggage in a completely different order. Taro tried to rearrange the luggage himself, but the pieces are heavy and moving them takes physical strength. Each piece can be moved from its current position to any place he likes, such as between other pieces or at either end, but moving a piece costs as much strength as that piece weighs. Taro does not have much strength, so he decided to find a way to place the luggage in order from lightest to heaviest while using as little strength as possible.

Input

n
x1 x2 ... xn

n is the number of pieces of luggage Taro has
x1 through xn are the weights of the pieces, currently placed in the order x1, x2, …, xn

Output

Print the minimum total strength S needed to place the luggage in order from lightest to heaviest. A newline must be printed at the end

Constraints

1 ≤ n ≤ 105
1 ≤ xi ≤ n (1 ≤ i ≤ n)
xi ≠ xj (1 ≤ i, j ≤ n and i ≠ j)
All input values are integers

Examples4

Example 1
Input
```
4
1 4 2 3
```
Expected output
```
4
```
Example 2
Input
```
5
1 5 3 2 4
```
Expected output
```
7
```
Example 3
Input
```
7
1 2 3 4 5 6 7
```
Expected output
```
0
```
Example 4
Input
```
8
6 2 1 3 8 5 4 7
```
Expected output
```
19
```