解题思路

• 将位置视为 1…n 的点，按给定序列依次“激活”。

• 规则：若当前没有已激活点，首次激活免费；之后每次若要激活的点与某个已激活点相邻（左右相差 1），则免费，否则需要一次“冷启动”。

• 因为激活顺序固定，最少冷启动次数是确定的：顺序扫描序列，判断该位置左右是否已有被激活的位置。

• 算法（贪心 + 模拟） 用长度为 n+2 的布尔数组标记已激活（两端加哨兵避免越界）。遍历序列：

  • 第一个元素直接标记为激活；
  • 其余对于 ai，若 visited[ai-1] 或 visited[ai+1] 为真，则免费；否则冷启动次数 +1。随后将 visited[ai] 置真。

题目内容

在一条线段上有编号为 $1$ ~ $n$ 的 $n$ 个位置，起始均未被激活。给定一个长度为 $n$ 、两两不同的序列 {$a_1,a_2,...,a_n$} ，表示按时间从早到晚依次尝试激活这些位置。

激活遵循“冷启动”机制：

• 若当前尚无任何已激活位置，则可以免费激活 $a_1$；

• 若已经存在已激活位置，在激活 $a_i$ 时：

  • 若 $a_i$ 与至少一个已激活位置相邻（即存在已激活的 $x$ 使得 $∣a_i-x∣=1$），则可以免费激活；
  • 否则，必须消耗 $1$ 次“冷启动”才能激活装置。

目标：使序列中的全部位置都被成功激活，要求“冷启动”的总次数尽可能少。请输出这一最少次数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t(1≤t≤10^4)$ 表示数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(1≤n≤2×10^5)$；

• 第二行输入 $n$ 个两两不同的整数 $a_1,a_2,...,a_n(1≤a_i≤n)$ 。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行输出一个整数，表示使整序列按规则依次激活所需的最少“冷启动”次数。

样例1

输入

2
5
3 1 5 2 4
3
2 1 3

输出

2
0

说明

在第一组样例中：

• 激活 $3$ (首次免费)。

• 激活 $1$，与已激活位置不相邻，消耗 $1$ 次冷启动。

• 激活 $5$ ，与已激活位置不相邻，消耗 $1$ 次冷启动。

• 激活 $2$ ，与 $1$ 相邻，免费；

• 激活 $4$ ，与 $5$ 相部，免费:

总计冷启动次数为 $2$ 。第二组中始终可与相邻位置衔接，故答案为 $0$ 。