题目描述

某班有 $n$ 名学生，学号分别为 $1\sim n$。体育课上需要整理队伍，目前所有学生站成一排，从左到右第 $i$ 个人学号是 $p_i$，$p$ 数组形成一个排列。为了使所有学生学号单调递增，体育老师可以任意进行如下操作：选择一个学生出列，并让他前往队伍最前方或最后方，然后让队伍对齐。

体育老师头脑简单四肢发达，于是他希望你能够帮忙。现给出排列 $p$，求体育老师将学生按顺序排好所需要进行的最小操作次数。

输入格式

从文件 arrange.in 中读入数据。

输入的第一行包含整数 $n$，表示学生个数。

第二行包含 $n$ 个整数 $p_i$，表示初始时学生学号的顺序。

输出格式

输出到文件 arrange.out 中。

一行一个整数，表示最小操作次数。

样例 1 输入

4
4 1 3 2

样例 1 输出

2

样例 1 解释

其中一种最优方案是，先让编号为 $3$ 的人前往最后方，再让编号为 $4$ 的人前往最后方。可以证明不存在更优的方案。

样例 2 输入

5
4 1 2 5 3

样例 2 输出

2

样例 2 解释

其中一种最优方案是，先让编号为 $4$ 的人前往最后方，再让编号为 $5$ 的人前往最后方。可以证明不存在更优的方案。

样例 3

见选手目录下的 arrange3.in 与 arrange3.ans。

该样例满足测试点 $3\sim 5$ 的限制。

样例 4

见选手目录下的 arrange4.in 与 arrange4.ans。

该样例满足测试点 $8\sim 10$ 的限制。

数据范围

对于所有测试数据，保证：$1\le n\le10^5$，$p$ 是一个 $1\sim n$ 的排列。

特殊性质 A：保证 $\forall 1\le i\le n,p_i=i$。