Minimizing Cost of Sorting a Sequence

Given a sequence of positive integers, you are allowed to perform operations that move a contiguous subsequence to any position. The cost of an operation is defined as the sum of the numbers in the moved subsequence. Your task is to sort the sequence in increasing order with the minimum total cost.

An equivalent formulation is: To achieve the sorted sequence, you can choose to not move a subsequence (which remains in its original order) and move the rest of the numbers. The cost will be the sum of the numbers that you move. Therefore, the optimal strategy is to find a subsequence that is in strictly increasing order and has the maximum possible sum; the minimum cost is then the total sum of the sequence minus this maximum sum.

For example, consider the sequence ({7, 1, 2, 3}). One possibility is to move (7) from the beginning to the end with a cost of (7). However, by leaving (7) in place and moving the contiguous block ({1, 2, 3}), the cost is (1+2+3=6), which is lower. Hence, the answer is 6.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the sequence.

The second line contains n positive integers separated by spaces.

It is guaranteed that the sum of the sequence fits within a 64-bit signed integer.

outputFormat

Output a single integer representing the minimum total cost required to sort the sequence in increasing order.

sample

4
7 1 2 3

6