최소 비용 정렬

정수 배열 하나를 비내림차순으로 정렬하려고 한다. 쓸 수 있는 연산은 하나뿐이다. 원소 하나를 배열에서 빼내어 다른 자리에 끼워 넣을 수 있고, 넣는 자리는 맨 앞, 맨 뒤, 인접한 두 원소 사이 중 어디든 된다. 연산 한 번의 비용은 옮긴 원소의 값과 같다.

배열을 비내림차순으로 만들 때까지 드는 비용의 합이 최소가 되도록 하고, 그 최솟값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 배열의 크기 $N$ ($1 \le N \le 100$)이 주어진다. 둘째 줄에는 배열의 원소 $N$개가 공백으로 구분되어 주어지고, 각 원소는 $1$ 이상 $1000$ 이하의 정수다.

각 테스트 케이스마다 배열을 정렬하는 데 드는 최소 비용을 한 줄에 하나씩 출력한다.