题目描述

给定一个由 $1$ 到 $N$ 的整数重新排列得到的数列 $(P_1, P_2, \ldots, P_N)$。你可以重复进行如下操作，将该数列变为升序排列，求所需操作次数的最小值。

• 每次操作可以选择数列中的一个元素，将其移动到数列的开头或末尾。

可以证明，使用上述操作一定可以将数列变为升序排列。

输入格式

输入通过标准输入给出，格式如下：

$N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

输出所需操作次数的最小值。

样例 1

输入

4
1
3
2
4

输出

2

样例 2

输入

6
3
2
5
1
4
6

输出

4

样例 3

输入

8
6
3
1
2
7
4
8
5

输出

5

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $(P_1, P_2, \ldots, P_N)$ 是 $(1, 2, \ldots, N)$ 的一个排列
• 输入均为整数

样例解释 1

例如，可以通过以下操作将数列变为升序排列：

• 将 $2$ 移动到开头。新数列为 $(2, 1, 3, 4)$。
• 将 $1$ 移动到开头。新数列为 $(1, 2, 3, 4)$。

由 ChatGPT 4.1 翻译