P7714 「EZEC-10」排列排序

给你一个长度为 $n$ 的排列 $p_1,p_2, \cdots ,p_n$。你需要把它排序。 每次可以花区间长度，即 $r-l+1$ 的代价，选择排列中的任意一段区间 $[l,r]$，并将 $[l,r]$ 从小到大排序。 现在你可以让他进行若干次这个操作，直到 $p$ 中元素的值从 $1$ 到 $n$ 按升序排序，即对于 $1$ 到 $n$ 的每一个 $i$，都有 $p_i=i$。 求问花的代价最少为多少？

无

无

【样例 $1$ 说明】 对于第一组数据，可选择区间 $[2,3]$ 进行排序。 对于第二组数据，可选择区间 $[1,3]$ 进行排序。 【数据规模与约定】 对于 $20\%$ 的数据，$n\leq 4$。 对于另 $30\%$ 的数据，$\sum n\leq5000$。 对于另 $10\%$ 的数据，$p_1=n$。 对于 $100\%$ 的数据，$1\le T,\sum n\le 10^6$。