记录编号	584974	评测结果	AAAAAAAAAA
题目名称	[YNOI2019] 排序	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.697 s
提交时间	2023-11-17 16:02:29	内存使用	1.63 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int a[100010],b[100010];
ll c[100010],f[100010];
void add(int x,ll w){
    for(int i=x;i<=m;i+=i&(-i)){
    	c[i]=max(c[i],w);
    }
    return;
}
ll query(int x){
    ll t=0;
	for(int i=x;i>0;i-=i&(-i)){
    	t=max(t,c[i]);
    }
    return t;
}
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		memset(c,0,sizeof(c));
		ll sum=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			b[i]=a[i];
			sum+=a[i];
		}
		sort(b+1,b+n+1);
		m=unique(b+1,b+n+1)-b-1;
		for(int i=1;i<=n;i++){
		    int x=lower_bound(b+1,b+m+1,a[i])-b;
		    f[i]=query(x)+a[i];
		    add(x,f[i]);
        }
        cout<<sum-query(m)<<endl;
	}
	return 0;
}