传送排序

Problem Description

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

• 将一个新的传送门插入到序列中。可以插入到序列中最左侧的物品（猫或传送门）的左侧，最右侧的物品的右侧，或任意两个物品之间。
• 选择一只猫和一个在序列中的传送门，将猫从其原本位置移除。然后，将猫插入到到传送门的左侧。如果传送门左侧有其他物品，则将猫插入到传送门与其左侧物品之间。
• 选择一只猫和一个在序列中的传送门，将猫从其原本位置移除。然后，将猫插入到到传送门的右侧。如果传送门右侧有其他物品，则将猫插入到传送门与其右侧物品之间。 在所有操作完成后，cats 会移除序列中所有的传送门，不改变序列中猫的相对位置。 cats 希望通过操作将猫按编号从小到大排序，即在所有操作结束后，从左到右第 $i$ 只猫的编号为 $i$。在此基础上，cats 希望最小化操作的总次数。你能告诉 cats 最少需要多少次操作才能将猫排序吗？

Input

第一行包含一个整数 $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$。

Output

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

Sample Input

5
1
1
3
2 3 1
7
1 3 2 4 6 5 7
6
6 5 4 3 2 1
15
14 12 6 7 1 3 5 8 11 13 15 9 10 4 2

Sample Output

0
2
4
6
12

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）