P17148 [ICPC 2017 Xi'an R] Naomi with Array

Now Naomi is facing another math problem. Naomi has an $1$-indexed array which contains $n$ different non-negative numbers. She needs to move the numbers to make the array in descending order. Each move Naomi can choose $i$, $j$ and move the number of position $i$ to position $j$ with cost $i+j$. Suppose she moves the number of position $i$ to position $j$: - If $i < j$, $A[i+1], A[i+2] \dots A[j]$ move to $A[i], A[i+1] \dots A[j-1]$ one by one. - If $i > j$, $A[j], A[j+1] \dots A[i-1]$ move to $A[j+1], A[j+2] \dots A[i]$ one by one. Naomi wants to minimize the sum of costs from each move. But it’s not enough, Naomi wants to know how many moves at least (also the sum of costs should be minimal).

The input contains multiple test cases. (No more than $20$) In each test case: The first line contains one number $n$ ($1 \le n \le 1000$). The following line contains $n$ numbers denoting array $A$. Each number in array $A$ will be less than $10^8$.

For each test case, print the minimum sum of the costs and the minimum moves in a single line. Separate them by one space.