希蒙爱排序

题目背景

希蒙最近学习了排序的算法，已经完全掌握了把一个无序的序列变成一个有序的序列的方法，但他觉得这也太无聊了，于是他打算换个花样。

题目描述

给定一个序列$a_1,a_2,a_3,\cdots,a_n$，你可以执行多次下述操作，将序列变成一个不下降序列，求最小进行的操作次数。

操作如下：

最初有一个空序列$B$。

1.若$A$不为空，则你可以从$A$的首位置或者尾位置选择一个数，将其从$A$中删除，并从尾部插入进$B$序列。重复此操作。

2.若$A$为空，则将$B$序列复制回$A$序列，清空$B$序列。

比如，原始$A$为1,3,7,2,3,6,9,5,3,8

则我们经过一次变化后，可以得到1,8,3,3,5,7,2,9,6,3，操作顺序分别为，首尾首尾尾首首尾尾尾。

输入格式

第一行一个整数$n$，表示序列长度。

第二行$n$个整数$a_i$，表示序列。

输出格式

你一共需要输出一个整数，表示将序列变成不下降序列的最小操作次数。

样例 #1

样例输入 #1

3
2 2 5

样例输出 #1

0

样例 #2

样例输入 #2

6
1 5 8 10 3 2

样例输出 #2

1

提示

数据范围：

对于10%的数据，我们保证$1<=n<=10$。

对于100%的数据，我们保证$1<=n<=3\cdot10^5,1<=a_i<=10^9$。