Bartek 是一位著名的电子音乐（techno）制作人，他目前正在完善他的下一首热门单曲。他创作了一首由 $n$ 个节拍组成的乐曲，编号依次为 $1$ 到 $n$。在音乐编辑软件中花费了数小时后，他正准备导出 mp3 文件，但他注意到这些节拍目前的排列顺序为 $a_1, a_2, \dots, a_n$。Bartek 需要将节拍排列为升序，即 $1, 2, \dots, n$。

该软件允许两种操作：

• 将最后一个节拍移动到任意位置，例如 $(2, 4, 1, 5, 3) \to (2, 3, 4, 1, 5)$。
• 将任意节拍移动到开头，例如 $(2, 4, 1, 5, 3) \to (5, 2, 4, 1, 3)$。

要将节拍按升序排列，最少需要多少次操作？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示节拍的数量。

第二行包含 $n$ 个两两不同的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$ 且 $a_i \ne a_j$)，表示程序中节拍当前的顺序。

输出格式

输出一个整数，表示所需的最少操作次数。

样例

输入样例 1

6
3 2 5 4 1 6

输出样例 1

4

输入样例 2

9
3 1 2 5 6 4 9 7 8

输出样例 2

6

说明

我们从节拍序列 $(3, 2, 5, 4, 1, 6)$ 开始。以下是一种通过四次操作达到目标顺序的方法：

• 将最后一个节拍向左移动两个位置：$(3, 2, 5, 6, 4, 1)$。
• 将节拍 2 移动到开头：$(2, 3, 5, 6, 4, 1)$。
• 将节拍 1 移动到开头：$(1, 2, 3, 5, 6, 4)$。
• 将最后一个节拍向左移动两个位置：$(1, 2, 3, 4, 5, 6)$。

也可以通过其他方式使用四次操作获得升序，但无法在三次操作内完成，因此结果为 4。