转载自：「题解：P14899 [ICPC 2018 Yokohama R] What Goes Up Must Come Down」

最后的数列是单峰的。

每个点显然要么在左边的坡上，要么在右边的坡上。

如果在左边的坡上，那么它左边的所有比它大的点都要与它交换。右边坡上同理。

于是正反各用树状数组对每个点求一遍以它为发端的逆序对数量即可得到每个点的每个选择的代价。

显然每个点取最优的代价进行选择，所有代价之和即为答案。

时间复杂度 $O(n\log n)$，做完了。

#include<bits/stdc++.h>
#define int long long
#define N 300000
#define lowbit(x) x&(-x)
using namespace std;
int a[300005];
int qz[300005];
int hz[300005];
int tr[300005];
int top;
void upd(int x){
    for(int i=x;i<=N;i+=lowbit(i))
    tr[i]++;
    top++;
}
int qry(int x){
    int ans=top;
    for(int i=x;i;i-=lowbit(i))
    ans-=tr[i];
    return ans;
}
signed main(){
    int n;
    cin>>n;
    map<int,int>mp;
    for(int i=1;i<=n;i++)
    cin>>a[i],mp[a[i]]=1;
    int qwq=0;
    for(auto i:mp)mp[i.first]=++qwq;
    for(int i=1;i<=n;i++)
    a[i]=mp[a[i]];
    int ans=0;
    for(int i=1;i<=n;i++)
    qz[i]=qry(a[i]),upd(a[i]);
    memset(tr,0,sizeof tr);top=0;
    for(int i=n;i;i--)
    hz[i]=qry(a[i]),upd(a[i]);
    for(int i=1;i<=n;i++)
    ans+=min(qz[i],hz[i]);
    cout<<ans;
    return 0;
}
//「接下来我每天都会在这间房子前面放食物，你们要记得吃。然后，这是生活费。」

// 官员先生把能足够生活几天的钱交到爱丽洁手中，对她说：
//「我会定期带钱来，你可以随意花用，钱用完了要马上跟我说。」

// 在你们的伤痛痊愈前，就让这个国家照顾你们吧
// ——他还这么对两姊妹说。

// 这个国家接纳了她们。

//「——可是住在这个国家的人好像不是这样。」