有 $n$ 只猫排成一个序列，从左到右第 $i$ 只猫的编号为 $p_i$，其中 $p$ 是一个 $1$ 到 $n$ 的排列。在一次操作中， cats 可以选择：

• 将一个新的传送门插入到序列中。可以插入到序列中最左侧的物品（猫或传送门）的左侧，最右侧的物品的右侧，或任意两个物品之间。
• 选择一只猫和一个在序列中的传送门，将猫从其原本位置移除。然后，将猫插入到到传送门的左侧。如果传送门左侧有其他物品，则将猫插入到传送门与其左侧物品之间。
• 选择一只猫和一个在序列中的传送门，将猫从其原本位置移除。然后，将猫插入到到传送门的右侧。如果传送门右侧有其他物品，则将猫插入到传送门与其右侧物品之间。

在所有操作完成后，cats 会移除序列中所有的传送门，不改变序列中猫的相对位置。

cats 希望通过操作将猫按编号从小到大排序，即在所有操作结束后，从左到右第 $i$ 只猫的编号为 $i$。在此基础上，cats 希望最小化操作的总次数。你能告诉 cats 最少需要多少次操作才能将猫排序吗？

第一行包含一个整数 $T$ （$1\leq T \leq 2\cdot 10^4$），表示一共有 $T$ 组测试数据。

对于每组测试数据：

第一行为一个整数 $n$ （$1\leq n\leq 2\cdot 10^5$），表示猫的总数。

第二行为 $n$ 个整数 $p_1,p_2,\dots,p_n$ （$1\leq p_i \leq n$），表示初始时猫的编号。保证 $p$ 是一个 $1$ 到 $n$ 的排列。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

对于每组测试数据，输出一个整数，表示 cats 最少需要的操作次数。