P4452.第1题-冷启动激活次数
题目内容
在一条线段上有编号为 1 ~ n 的 n 个位置，起始均未被激活。给定一个长度为 n 、两两不同的序列 {a1,a2,...,an} ，表示按时间从早到晚依次尝试激活这些位置。
激活遵循“冷启动”机制：
目标：使序列中的全部位置都被成功激活，要求“冷启动”的总次数尽可能少。请输出这一最少次数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≤t≤104) 表示数据组数，每组测试数据描述如下：
-
第一行输入一个整数 n(1≤n≤2×105)；
-
第二行输入 n 个两两不同的整数 a1,a2,...,an(1≤ai≤n) 。
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
对于每组测试数据，新起一行输出一个整数，表示使整序列按规则依次激活所需的最少“冷启动”次数。
样例1
输入
2
5
3 1 5 2 4
3
2 1 3
输出
2
0
说明
在第一组样例中：
总计冷启动次数为 2 。第二组中始终可与相邻位置衔接，故答案为 0 。
