### Problem Statement

We have an array A and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array.

For example, we have an array {7, 1, 2, 3}. We can sort it by moving 7 from the head to the tail. But the cost of this operation is 7 which is not optimal. The optimal sorting algorithm is to consecutively move 1, 2 and 3 to the proper places before 7. The total cost of these three movements will be 1+2+3=6, which is less than 7.

You will be given a int[] theArray. Return the minimal total cost required to sort the array.

### Definition

 Class: InsertSort Method: calcMinimalCost Parameters: int[] Returns: int Method signature: int calcMinimalCost(int[] theArray) (be sure your method is public)

### Constraints

-theArray will contain between 1 and 50 elements, inclusive.
-Each element of theArray will be between 1 and 1000, inclusive.

### Examples

0)

 `{7, 1, 2, 3}`
`Returns: 6`
 The example from the problem statement.
1)

 `{7, 1, 2, 5}`
`Returns: 7`
 The cheapest way to sort the array is to move 7 from the head to the tail.
2)

 `{1, 8, 8, 12, 99}`
`Returns: 0`
3)

 `{8, 2, 6, 5, 1, 4}`
`Returns: 18`
4)

 `{6, 4, 5, 3, 8, 2, 7, 2, 11, 2, 2}`
`Returns: 24`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4844

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10675&pm=4844

Andrew_Lazarev

#### Testers:

PabloGilberto , brett1479 , Olexiy

#### Problem categories:

Dynamic Programming