Description

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?

Input Format

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 Format

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

2
3
1 3 2
4
3 2 1 4

2
3

Hint

[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