杭电/2025-6/1004 传送排序

题目描述

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

• 插入一个新的传送门到序列中。可以插入到最左侧物品的左侧、最右侧物品的右侧，或任意两个物品之间。
• 选择一只猫和一个传送门，将这只猫从原位置移除，再插入到该传送门左侧（若左侧有物品，则插在两者之间）。
• 选择一只猫和一个传送门，将这只猫从原位置移除，再插入到该传送门右侧（若右侧有物品，则插在两者之间）。

所有操作完成后，cats 会移除序列中的所有传送门，且不改变猫之间的相对顺序。

cats 希望最终把猫按编号从小到大排序，即最终从左到右第 $i$ 只猫编号为 $i$。在此基础上，cats 希望操作总次数最少。请你求出最少操作次数。

输入输出格式

输入

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行一个整数 $n$，表示猫的数量。

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

输出

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

样例

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

0
2
4
6
12

数据范围

• $1 \le T \le 2 \times 10^4$
• $1 \le n \le 2 \times 10^5$
• $1 \le p_i \le n$
• 保证 $p$ 是一个 $1$ 到 $n$ 的排列
• 所有测试数据的 $n$ 之和不超过 $10^6$