记录编号	584946	评测结果	AAAAAAAAAA
题目名称	[YNOI2019] 排序	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.874 s
提交时间	2023-11-17 14:05:26	内存使用	83.55 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 1e7+10;
int t,n;
ll c[M],a[N],f[N];
ll ask(ll x){
    ll ans = 0;
    for(;x > 0;x -= x & -x)ans = max(ans,c[x]);
    return ans;
}
void add(ll x,ll y){
    for(;x <= 1e7;x += x & -x)c[x] = max(c[x],y);
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        ll ma = 0,sum = 0;
        for(int i = 1;i <= 1e7;i++)c[i] = 0;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
            scanf("%lld",&a[i]),sum += a[i],ma = max(ma,a[i]);
        for(int i = 1;i <= n;i++){
            f[i] = a[i] + ask(a[i]);
            add(a[i],f[i]);
        }
        printf("%lld\n",sum-ask(ma));
    }
    
    
    return 0;
}