学过排序后的喵喵也突发奇想，想到了一种对数组排序的方法，喵喵对数组排序只有两种操作：

• 从数组中挑选一个元素，然后讲其移至数组的尾部
• 从数组中挑选一个元素，然后将其移至数组的头部

例如对于一个包含 $n$ 个元素的数组： $a1​,a2​,⋯,ai−1​,ai​,ai+1​,⋯,an​$

• 如果应用了第一个操作，数组会变成： $a1​,a2​,⋯,ai−1​,ai+1​,⋯,an​,ai​$
• 如果应用了第二个操作，数组会变成： $ai​,a1​,a2​,⋯,ai−1​,ai+1​,⋯,an​$

事实证明，用这两个操作一定可以在有限次内将数组从小到大排列。

现在给出一个数组，喵喵想知道最少操作几次才能将数组从小到大排列。

输入格式

第一行输入一个正整数 $n$，代表数组中元素的个数

第二行给出 $n$ 个正整数 $ai​$，代表数组中的元素

输出格式

在一行中输出将数组从小到大排序所需的最小次数

样例输入

5
3 1 2 4 5

样例输出

2

样例输入2

5
5 4 3 2 1

样例输出2

4

样例输入3

6
2 3 1 6 4 5

样例输出3

2

提示

样例解释1：

第一步将$2$移到开头，第二步将$1$移到开头

样例解释2：

可以让$5$不动，然后将$4，3，2，1$依次移到开头

也可以让$1$不动，然后将$2，3，4，5$依次移到末尾

操作次数都是$4$次

样例解释3：

第一步将1移动到开头，第二步将6移动到末尾，操作次序可以交换

数据规模与约定：

• 子任务 $1$ 有 $10$分，满足 $n≤10$

• 子任务 $2$ 有 $10$ 分，满足$n≤300$ 且 $ai​$ 互不相同

• 子任务 $3$ 有 $15$ 分，满足 $n≤5000$ 且 $ai​$ 互不相同

• 子任务 $4$ 有 $20$ 分，满足 $ai$​ 互不相同

• 子任务 $5$ 有 $10$ 分，满足 $n≤300$

• 子任务 $6$ 有 $15$ 分，满足 $n≤5000$

• 子任务 $7$ 有 $20$分，无特殊性质

对所有的测试数据都满足 $1≤n≤3⋅10^5,1≤ai​≤10^9$