#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=100000+5;
int n,m;
int a[N],b[N];
ll c[N],f[N];
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);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(c,0,sizeof(c));
		ll sum=0;
		for (int i=1;i<=n;i++)scanf("%d",&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]);
        }
        printf("%lld\n",sum-query(m));
	}return 0;
}