题目描述

一个递增数组是指这个数组中的每一项(除了第一项)都大于他前面那一项。

数组的旋转是指将一个数组的最后若干项移动到数组的最前面，即把数组{a[1],a[2]...a[n]} 变成 {a[k],a[k+1]...a[n],a[1]...a[k-1]}. (1 <= k <= n)

现在有一个1到N这N个数字组成的数组，你可以改变其中若干项的位置，最后要使得这个数组递增或者旋转后递增。

比如说，对于数组: {1,3,4,5,6,2}. 我们可以改变第一项和最后一项的位置以得到 {2,3,4,5,6,1} ，这个数组在旋转以后可以变成递增数组 {1,2,3,4,5,6} 。
当然我们也可以直接改变后5项的位置以得到 {1,2,3,4,5,6};
或者改变前5项位置以得到 {3,4,5,6,1,2};
或者改变全部6项的位置以得到 {4,5,6,1,2,3};
或者改变全部6项的位置以得到 {5,6,1,2,3,4};
或者改变全部6项的位置以得到 {6,1,2,3,4,5};
这些都是可以的, 但最少需要改变的位置数是2，也就是第一种情况。

你的任务就是对于给定的数组找出最少需要改变的位置数，使得这个数组递增或者旋转后递增。

输入要求

第一行一个整数N，表示数组长度。 (1 <= N <= 10^5)
第二行是N个互不相等的整数a[i]，表示数组的元素。 (1 <= a[i] <= N)

输出要求

输出一个整数，表示最少需要改变的位置数。

输入样例

5
5 4 3 2 1

输出样例

4

提示

改变x个数的位置就是说有x个数的位置被改变了=。=|||

来源

NBU OJ