你有 $n$ 本书从左到右排列在书架上。这些书的编号从 $1$ 到 $n$ 互不相同。从左往右数第 $i$ 本书的编号为 $p_i$。你希望对这些书进行排序，使得它们的编号从左到右呈升序排列。

在一步操作中，你可以执行以下任一动作： 选择两本相邻的书并交换它们。 选择一本书并将其移动到最左侧。 * 选择一本书并将其移动到最右侧。

计算将这些书排序所需的最少步数。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)。第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)。

输出格式

输出将书按编号从左到右升序排列所需的最少步数。

样例

样例输入 1

6
6 2 1 4 3 5

样例输出 1

3

说明 1

你可以按顺序执行以下三步操作：交换编号为 2 和 1 的书，交换编号为 4 和 3 的书，并将编号为 6 的书移动到最右侧。

$6\ 2\ 1\ 4\ 3\ 5 \to 6\ 1\ 2\ 4\ 3\ 5 \to 6\ 1\ 2\ 3\ 4\ 5 \to 1\ 2\ 3\ 4\ 5\ 6$

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

样例输入 2

9
9 2 4 3 7 5 1 8 6

样例输出 2

5