#2340. 希蒙爱排序

希蒙爱排序

希蒙爱排序

题目背景

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

题目描述

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

操作如下:

最初有一个空序列BB

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

2.若AA为空,则将BB序列复制回AA序列,清空BB序列。

比如,原始AA为1,3,7,2,3,6,9,5,3,8

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

输入格式

第一行一个整数nn,表示序列长度。

第二行nn个整数aia_i,表示序列。

输出格式

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

样例 #1

样例输入 #1

3
2 2 5

样例输出 #1

0

样例 #2

样例输入 #2

6
1 5 8 10 3 2

样例输出 #2

1

提示

数据范围:

对于10%的数据,我们保证1<=n<=101<=n<=10

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