说明

书架上有从左到右排列的 $n$ 本书。这些书的标签互不相同，为 $1$ 到 $n$。从左数第 $i$ 本书的标签为 $p_i$。你需要对书本进行排序，使得它们的标签从左到右按升序排列。每一步，你可以执行以下操作之一：

• 选择两本相邻的书并交换它们。
• 选择一本书并将其移动到最左边位置。
• 选择一本书并将其移动到最右边位置。

计算排序所需的最少步数。

输入格式

输入的第一行包含一个整数 $n$（$2\le n\le 500\,000$）。第二行包含 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1\le p_i\le n$）。

输出格式

输出按标签从左到右升序排序所需的最少步数。

6
6 2 1 4 3 5

3

9
9 2 4 3 7 5 1 8 6

5

提示

样例输入/输出 #1 的解释

你可以按顺序执行以下三步：交换标签为 $2$ 和 $1$ 的书，交换标签为 $4$ 和 $3$ 的书，然后将标签为 $6$ 的书移动到最右边位置。

$\begin{aligned}6 \ 2 \ 1 \ 4 \ 3 \ 5 &\rightarrow 6 \ \mathbf{1} \ \mathbf{2} \ 4 \ 3 \ 5 \\&\rightarrow 6 \ 1 \ 2 \ \mathbf{3} \ \mathbf{4} \ 5 \\&\rightarrow 1 \ 2 \ 3 \ 4 \ 5 \ \mathbf{6}\end{aligned}$

可以证明两步或更少的步数不足以完成排序。

翻译由 DeepSeek 完成