E-奇怪的排序_第二届“重科杯”重庆科技大学程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

star 最近在研究奇怪的排序，他给定一个长度为 $n$ 的排列 $a$ ，你可以做如下操作任意多次：

每次选择一个区间 $[l,r]$ ： $a_l,a_{l+1},...,a_r$ ，对他们进行重排，假设重排后为： $a'_l,a'_{l+1},...,a'_r$ ，要求对于 $\forall i\in[l,r]$ ，都要满足 $a_i\not=a'_i$ 。

现在 star 问你，最少操作几次，可以把这个排列变为： $1,2,3,...,n$ 。

本题有多组测试数据。

先输入 ，表示数据组数。

对于每组数据：

第  行输入 ，表示序列的长度。

第  行输入  个整数 ，保证序列  是一个排列。

数据保证  组数据的 。

对于每组数据，输出最小操作次数。

示例1

复制

复制

0
1

第  组数据，由于已经按要求排列，所以最小操作次数为 。

第  组数据，显然可以选择区间 ，重排前：，重排后：，且满足重排的条件，操作完后序列已经按要求排列，所以最小操作次数为 。