#include<stdio.h>
#include<algorithm>
constexpr int inf{1000000000};
constexpr int N{1000};
int h[N+5],f[N+5];
int cl[N+5],cr[N+5];
int buc[(N<<1)+5];
void solve() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",h+i);
    }
    std::fill(f+1,f+n+1,inf),f[0]=0;
    for(int i=1;i<=n;i++) {
        cl[i]=cr[i]=0;
        for(int l=i-1,r=i+1;1<=l&&r<=n;l--,r++) {
            cl[l]=0,cr[l]=h[r]>h[l];
            cr[r]=0,cl[r]=h[l]>h[r];
            for(int j=l+1;j<=r-1;j++) {
                cl[j]+=h[l]>h[j],cr[j]+=h[r]>h[j];
                cr[l]+=h[j]>h[l],cl[r]+=h[j]>h[r];
            }
            int lim{r-l};
            std::fill(buc,buc+(lim<<1)+1,0);
            int sum{0};
            for(int j=l;j<=r;j++) {
                sum+=cl[j];
                if(cl[j]||cr[j]) {
                    ++buc[cr[j]-cl[j]+lim];
                }
            }
            for(int j=0,c=0;j<=lim<<1&&c<r-l>>1;j++) {
                while(c<r-l>>1&&buc[j]>0) {
                    sum+=j-lim,++c,--buc[j];
                }
            }
            f[r]=std::min(f[r],f[l-1]+sum);
            if(sum>n/3+10) {
                break;
            }
        }
    }
    printf("%d\n",f[n]);
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        solve();
    }
    return 0;
}