题目描述

小 E 给你一个长度为 $n$ 的排列 $p_1,p_2, \cdots ,p_n$ 。小 E 想要把它排序。

小 E 每次可以花区间长度，即 $r-l+1$ 的代价，选择排列中的任意一段区间 $[l,r]$ ，并将 $[l,r]$ 从小到大排序。

现在你可以让他进行若干次这个操作，直到 $p$ 中元素的值从 $1$ 到 $n$ 按升序排序，即对于 $1$ 到 $n$ 的每一个 $i$ ，都有 $p_i=i$ 。

小 E 问你，他花的代价最少为多少？

输入格式

本题有多组询问，第一行有一个数 $T$ 表示询问组数。

对于每组询问：

第一行给出一个整数 $n$ 。

第二行 $n$ 个整数，由空格隔开，代表排列 $p$ 中元素的值。

$T$ 行，每行一个整数表示一组询问的答案。

2
3

2
10
2 1 3 4 9 5 6 7 8 10
9
2 1 3 4 9 5 6 7 8

7
7

【样例 $1$ 说明】

对于第一组数据，可选择区间 $[2,3]$ 进行排序。

对于第二组数据，可选择区间 $[1,3]$ 进行排序。

【样例 $2$ 说明】

对于第一组数据，需要选择区间 $[1,2] [5,9]$ 进行排序 , 答案是 7 。

对于第二组数据，可选择区间 $[1,2] [5,9]$ 进行排序 , 答案是 7 。

【数据规模与约定】

对于 $100\%$ 的数据， $1\le T,\sum n\le 10^6$ 。