题意：

顺序操作一个长度为 \(n\) 的序列 \(a_i\) ，每次可以选择将第 \(i\) 个放到一个初始为空的双端队列的最前或最后，希望进行完 \(n\) 次操作后逆序对数量最小化。

思路：

考虑贪心地放，每次计算放在最前或最后会增加的逆序对数量，选择较小的放置；

这个贪心的正确性显然，如果第 \(i+1\) 个放前面，则无论如何第 \(i\) 个都在第 \(i+1\) 个以后，反之如果第 \(i+1\) 个放在最后，则第 \(i\) 个一定在其之前，所以前一个的怎么放对后面的贡献都相同，放最好的就行；

求逆序对就数据结构维护一下修改和查询排名，我写的离散化后线段树。

代码：

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,a[(int)(2e5+10)],t[(int)(1e6+10)],b[(int)(2e5+10)];
void add(int u,int st,int ed,int id,int k)
{
    if(st==ed) 
    {
        t[u]+=k;
        return ;
    }
    int mid=(st+ed)>>1;
    if(mid>=id) add(u*2,st,mid,id,k);
    else add(u*2+1,mid+1,ed,id,k);
    t[u]=t[u*2]+t[u*2+1];
}
int sum(int u,int st,int ed,int l,int r)
{
    if(l<=st&&r>=ed) return t[u];
    if(l>ed||r<st) return 0;
    int mid=(st+ed)>>1;
    return sum(u*2,st,mid,l,r)+sum(u*2+1,mid+1,ed,l,r);
}
signed main()
{
    int q;cin>>q;
    while(q--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
        // for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        // puts("");
        int ans=0;
        memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++)
        {
            int cnt1=sum(1,1,n,a[i]+1,n),cnt2=sum(1,1,n,1,a[i]-1);
            ans+=min(cnt1,cnt2);
            add(1,1,n,a[i],1);
        }
        cout<<ans<<"\n";
    }
}