시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 0 0 0.000%

문제

We have an array 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. You are to write a program that will find the minimum cost to sort such an array.

 

입력

First line of the input contains T the number of test cases. For each test case the first line contains an integer N (1 ≤ N ≤ 100). The second line contains N positive integers separated by spaces. These integers denote the array. Each of these integers is between 1 and 1000 inclusive.

출력

For each case, the output contains an integer denoting the minimum cost to sort the array.

예제 입력

3
4
7 1 2 3
4
7 1 2 5
6
8 2 6 5 1 4

예제 출력

6
7 
18 

힌트