写一波题解，WA了N多次==
看到这题感觉像最长上升子序列，然后还真是，用N-len（最长上升子序列长度就行了）；
但这个范围就奇坑无比
一般n³只能过500左右
n²只能过1000左右
然后这个数据是50000，必须要nlogn的时间复杂度
根据之前的求最长上升子序列是递推公式
F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。
但n²只能过50分；后面都会超时
##################################
nlogn的做法：
引用链接：http://blog.csdn.net/darwin_/article/details/38360997

引用的！！！！！！！！！！！！！！！！

设 A[t]表示序列中的第t个数，F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度，初始时设F [t] = 0(t = 1, 2, ..., len(A))。则有动态规划方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。

现在，我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < t
(2)A[x] < A[y] < AtF[x] = F[y]

此时，选择F[x]和选择F[y]都可以得到同样的F[t]值，那么，在最长上升子序列的这个位置中，应该选择A[x]还是应该选择A[y]呢？

很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[t-1]这一段中，如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。
再根据条件(3)，我们会得到一个启示：根据F[]的值进行分类。对于F[]的每一个取值k，我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值，即D[k] = min{A[t]} (F[t] = k)。

注意到D[]的两个特点：
(1)　D[k]的值是在整个计算过程中是单调不下降的。
(2)　D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。

利 用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A [t] > D[len]，则将A[t]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A [t]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[t]。令k = j + 1，则有A [t] <= D[k]，将A[t]接在D[j]后将得到一个更长的上升子序列，更新D[k] = A[t]。最后，len即为所要求的最长上 升子序列的长度。

在 上述算法中，若使用朴素的顺序查找在D[1]..D[len]查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的 时间复杂度为O(n^2)，与原来的算法相比没有任何进步。但是由于D[]的特点(2)，我们在D[]中查找时，可以使用二分查找高效地完成，则整个算法 的时间复杂度下降为O(nlogn)，有了非常显著的提高。需要注意的是，D[]在算法结束后记录的并不是一个符合题意的最长上升子序列！

##############################自己瞎掰的，可能写的又差又难懂，可省略，哈哈

d【i】表示的是原序列中长度为【i】的子序列中上升幅度最小的值
比如 原序列 1 3 9 7 8中
长度为3的递增子序列有 1 3 9 // 1 3 7
那么d【3】要存7，因为7结尾的递增子序列更有潜力变成最长子序列
最后一个数为8；1,3,9后面就接不了8了，但1,3,7能。
如何维护
对于序列 1 3 7 5 8 10 9 15 14 20
一开始d【1】=1；
由于3大于1，len++；d【len】=3；d={1,3}；len=2；（因为d【len】能够到达len的长度，所以大于d【len】的能够达到len+1的长度，所以len++）
由于7大于3，len++；d【len】=7；d={1,3,7}len=3；
由于5小于7，找到比5小中的数中的最大值为3，把3后面的数替换掉，a【3】=5；（因为d序列是递增的，所以找到k满足d【k】是小于a【i】中的数中的最大值，那么一定满足d【k+1】》a【i】，而这两个数都能满足k+1的最长子序列长度，但a【i】更小，更有潜力成为最长，所以d【k+1】=a【i】）
由于8大于5 所以len++ d【len】=8；d={1,3,5,8}len=4
以此类推
求得的len便是最长子序列长度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read()
{
    int x=0;
    char ch=getchar();
    while((ch<'0')||(ch>'9')){ch=getchar();}
    while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int d[500001],a[500001];
int efda(int left,int right,int x)//查找比x大的第一个数 
{
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        if(x<=d[mid])
        {
            right=mid-1;
        }
        else left=mid+1;
    }
    return left;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)//用a来储存序列 
    {
        cin>>a[i];
    }
    d[1]=a[1];
    int len=1; 
    for(int i=2;i<=n;i++)  //维护d数组 
    {                   //d【i】表示的是在最长子序列为i时的a【i】的最小值 
        int j;
        if(a[i]>d[len]){len++;j=len;}
        else{j=efda(1,len,a[i]);}
        d[j]=a[i];
    }
    cout<<(n-len)<<endl;
    return 0;
}