问题背景

我们称一个大小为 $n$ 的数列 $p_1, p_2, \ldots, p_n$ 是一个排列，当且仅当整数 $1 \sim n$ 在排列 $p$ 中均出现恰好一次。比如：

• $[1, 2, 3, 4]$ 是一个大小为 $4$ 的排列；
• $[5, 3, 2, 4, 1, 6, 7]$ 是一个大小为 $7$ 的排列；
• $[2]$，$[1, 3, 4, 3]$，$[1, 3, 4, 5, 6]$ 都不是排列。

题目描述

给定一个大小为 $n(1 \le n \le 10^5)$ 的排列 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$ 且对于任意 $i \neq j$，有 $p_i \neq p_j$）。

你可以对排列进行任意次操作，每次操作，你可以选择如下两种类型的操作之一进行操作：

• 操作1：选择任意一个下标 $i$，并将 $p_i$ 移动到排列的最前面，前 $i-1$ 个元素顺序右移一个位置；
• 操作2：选择任意一个下标 $i$，并将 $p_i$ 移动到排列的最后面，后 $n-i$ 个元素顺序左移一个位置。

例如：

• 若当前的排列为 $p = [1, 6, 4, 5, 2, 3]$，则选择操作1将 $p_5 = 2$ 交换到最前面后，排列变为 $p = [2, 1, 6, 4, 5, 3]$；
• 若当前的排列为 $p = [2, 7, 1, 5, 3, 4, 6]$，则选择操作2将 $p_2 = 7$ 交换到最后面后，排列变为 $p = [2, 1, 5, 3, 4, 6, 7]$。

你希望使用最少的操作次数，使排列变为升序（即使排列 $p$ 变为 $[1, 2, 3, \ldots, n]$，即对于任意 $1 \le i \le n$，有 $p_i = i$）。

求：使排列变为升序所需的最少操作次数。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$，表示排列大小。

第二行，$n$ 个整数 $p_1, p_2, \ldots, p_n$。表示一个大小为 $n$ 的排列。

输出格式

输出一个整数，表示使排列变为升序的最少操作次数。

5
4 1 2 5 3

2

6
2 1 3 4 6 5

2

说明/提示

样例解释

样例1：

初始时排列 $p = [4, 1, 2, 5, 3]$；

可以先通过操作2将 $p_1 = 4$ 交换到最后面，操作后 $p = [1, 2, 5, 3, 4]$；

再进行一次操作2将此时的 $p_3 = 5$ 交换到最后面，操作后 $p = [1, 2, 3, 4, 5]$，此时排列升序。

样例2：

初始时排列 $p = [2, 1, 3, 4, 6, 5]$；

可以先通过操作1将 $p_2 = 1$ 交换到最前面，操作后 $p = [1, 2, 3, 4, 6, 5]$；

再通过操作2将 $p_5 = 6$ 交换到最后面，操作后 $p = [1, 2, 3, 4, 5, 6]$，此时排列升序。

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$；
• 对于 $40\%$ 的数据，$n \le 100$；
• 对于 $60\%$ 的数据，$n \le 1000$；
• 对于 $80\%$ 的数据，$n \le 10^4$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，且保证 $p_1, p_2, \ldots, p_n$ 是一个大小为 $n$ 的排列。