#D7129. House Moving
House Moving
House Moving
Taro has decided to move. Taro has a lot of luggage, so I decided to ask a moving company to carry the luggage. Since there are various weights of luggage, I asked them to arrange them in order from the lightest one for easy understanding, but the mover left the luggage in a different order. So Taro tried to sort the luggage, but the luggage is heavy and requires physical strength to carry. Each piece of luggage can be carried from where it is now to any place you like, such as between other pieces of luggage or at the edge of the piece of luggage, but carrying one piece of luggage uses as much physical strength as the weight of that piece of luggage. Taro doesn't have much physical strength, so I decided to think of a way to arrange the luggage in order from the lightest one without using as much physical strength as possible.
Constraints
1 ≤ n ≤ 105 1 ≤ xi ≤ n (1 ≤ i ≤ n) xi ≠ xj (1 ≤ i, j ≤ n and i ≠ j)
- All inputs are given as integers
Input
n x1 x2 ... xn
- n represents the number of luggage that Taro has
- x1 to xn represent the weight of each piece of luggage, and are currently arranged in the order of x1, x2, ..., xn.
Output
S
- Output the total S of the minimum physical strength required to arrange the luggage in order from the lightest, but output the line break at the end
Examples
Input
4 1 4 2 3
Output
4
Input
5 1 5 3 2 4
Output
7
Input
7 1 2 3 4 5 6 7
Output
0
Input
8 6 2 1 3 8 5 4 7
Output
19
inputFormat
inputs are given as integers
Input
n x1 x2 ... xn
- n represents the number of luggage that Taro has
- x1 to xn represent the weight of each piece of luggage, and are currently arranged in the order of x1, x2, ..., xn.
outputFormat
Output
S
- Output the total S of the minimum physical strength required to arrange the luggage in order from the lightest, but output the line break at the end
Examples
Input
4 1 4 2 3
Output
4
Input
5 1 5 3 2 4
Output
7
Input
7 1 2 3 4 5 6 7
Output
0
Input
8 6 2 1 3 8 5 4 7
Output
19
样例
8
6 2 1 3 8 5 4 719