CF605A Sorting Railway Cars

一列无限长的铁道上有一列火车，这列火车由 $n$ 节车厢组成，编号从 $1$ 到 $n$（所有车厢的编号互不相同），并且这些车厢的排列顺序是任意的。David Blaine 想要将所有车厢按编号递增的顺序排列好。每次操作，他可以让任意一节车厢从当前位置消失，并将其随意传送到列车的最前端或最末端。请问最少需要多少次操作，David Blaine 才能将火车车厢按顺序排列好？

输入的第一行包含整数 $n$（$1 \leq n \leq 100000$），表示火车的车厢数量。 第二行包含 $n$ 个整数 $p_i$（$1 \leq p_i \leq n$，对于 $i \neq j$ 有 $p_i \neq p_j$），表示当前列车中各个车厢的编号排列顺序。

输出一个整数，表示将火车车厢排序所需的最小操作次数。

在第一个样例中，你需要先把第 $4$ 节车厢传送到列车末端，然后将第 $5$ 节车厢传送到列车末端。 由 ChatGPT 5 翻译