题目描述

给一个 $1$ 到 $n$ 的排列 $p$，你可以使用两种操作：

• 轮回：交换 $p$ 中相邻的两个位置。
• 疯狂：删除 $p$ 中的最小值。如果 $p$ 为空则不能进行操作。

问最少需要多少次操作才能使得序列单调递增。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数，描述排列 $p$。

输出格式

一行一个正整数，表示答案。

3
3 2 1

2

提示

样例解释：先删除 $p_3$，再交换 $p_1,p_2$。

本题采用捆绑测试。

数据范围：

• Subtask 1 (10pts)：$n\le 3$。
• Subtask 2 (30pts)：$n\le 10^3$。
• Subtask 3 (10pts)：$p_i=n-i+1$。
• Subtask 4 (50pts)：无特殊限制。

对于全部数据，$1\le n\le 10^5$，$p$ 是 $1$ 到 $n$ 的排列。