P7714 "EZEC-10" Permutation Sorting

You are given a permutation $p_1,p_2,\cdots,p_n$ of length $n$. You need to sort it. Each time, you may pay a cost equal to the length of the interval, i.e. $r-l+1$, choose any interval $[l,r]$ in the permutation, and sort $[l,r]$ in increasing order. Now you can perform this operation several times until the values in $p$ are sorted in increasing order from $1$ to $n$, that is, for every $i$ from $1$ to $n$, we have $p_i=i$. What is the minimum total cost?

This problem has multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$. The second line contains $n$ integers separated by spaces, representing the values of the permutation $p$.

Output $T$ lines, each containing one integer representing the answer for one test case.

[Sample $1$ Explanation] For the first test case, you can choose the interval $[2,3]$ to sort. For the second test case, you can choose the interval $[1,3]$ to sort. [Constraints] For $20\%$ of the testdata, $n\leq 4$. For another $30\%$ of the testdata, $\sum n\leq 5000$. For another $10\%$ of the testdata, $p_1=n$. For $100\%$ of the testdata, $1\le T,\sum n\le 10^6$. Translated by ChatGPT 5