You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

David 与和谐号

题目信息

时间限制: 1s

空间限制: 256M

输入文件: david.in

输出文件: david.out

题目描述

David管理了$n$辆火车，每辆火车都有一个$1$~$n$的编号且两两编号不同。今天这$n$辆火车在轨道上排错位置了，从左往右看，这些火车的编号分别为$A_1$，$A_2$，...，$A_n$。正常情况下，火车的编号从左往右应该是$1$，$2$，...，$n$。David为了快速地排好火车下班，他使出了超能力——将从左开始数的前$i$辆火车的位置进行翻转，也就是对序列的$A_1$，$A_2$，...，$A_i$进行翻转。例如原火车序列为$6,1,2,5,3,4$，对前$4$辆火车翻转，就会得到火车序列$5,2,1,6,3,4$

摸鱼人都知道要低调，David想知道，他最少要发动多少次超能力，才能使得火车的编号从左往右为$1$，$2$，...，$n$

输入格式

第一行一个整数 $T$ 表示数据组数。

每组数据第一行一个整数 $n$，第二行 $n$ 个整数 $A_1, A_2, \dots, A_n$。

输出格式

每组数据输出一行一个整数表示最少的翻转次数。

样例

样例输入1

1
8
8 6 1 3 2 4 5 7

样例输出1

7

数据范围与提示

• 对于测试点 $1,2$，$n=5$
• 对于测试点 $3,4$，$n=6$
• 对于测试点 $5,6$，$n=7$
• 对于测试点 $7,8,9$，$n=8$
• 对于测试点 $10$，$n=9$
• 对于测试点 $11$，$n=10$
• 对于测试点 $12\leq i\leq 21$，$n=i$
• 对于测试点 $22,23$，$n=22$
• 对于测试点 $24,25$，$n=23$
• 对于 100% 的测试数据，$T=5, n\leq 25$