学步园

题目链接：Click here~~

题意：

给一个长度为 n 的序列。

定义操作为每次选一个数，移动到序列的最前面。

问最少要多少次操作，可以使整个序列递增。

解题思路：

考虑如果已经选定了要选 {a,b,c} 三个数移动，那么我可以自由的调整移动的顺序，使移动之后的 {a,b,c} 升序排列。

所以可以想到，最多会移动 n 个数。

进一步想，其实最大的那个数不需要移动，即移动 n - 1 个数就可以了。

再进一步，如果次大数出现在了最大数的前面，那么次大数也不需要移动了。

......

受到启发，如果我们知道最多有多少个数不需要移动，那么把剩下的数每个移动一次就可以保证升序了。

而一个数能够不移动的必要条件是：比它大的数都不移动。

所以，在原序列从后向前中找一个关于递增后的后缀连续序列的最长公共子序列就行了。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 3e5 + 5;

int a[N],b[N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        memcpy(b,a,sizeof(a));
        sort(b,b+n);
        int ans = n;
        for(int i=n-1,j=n-1;i>=0;i--)
            if(a[i] == b[j])
            {
                j--;
                ans--;
            }
        printf("%d\n",ans);
    }
    return 0;
}