好题，但是感觉写起来有点屎。
题目大意
给定一个序列 \(a\)，你每次可以选择 \(i \in [1,n-1]\)，交换 \(a_i,a_{i+1}\)，并且给 \(a_i,a_{i+1}\) 取相反数。
问你最少需要多少次交换才能使得序列非降，可能无解。
做法
首先考虑给偶数位置初始乘上 \(-1\)，然后操作变成交换相邻两个数，下面提到的序列都是进行了这个操作之后的，最后需要使得：
- 对于奇数 \(i\)，满足 \(a_i+a_{i+1} \leq 0\)。
- 对于偶数 \(i\)，满足 \(a_i+a_{i+1} \geq 0\)。
然后发现 \(2i-1,2i\) 中必然有一个是非正数，\(2i,2i+1\) 中必然有一个非负数。
容易证明最后的序列肯定存在一个位置 \(p\) 满足：
- \(\forall i \in [2,p]\)，\(|a_{i-1}| \geq |a_i|\)，且 \(a_{i-1}\) 和 \(a_i\) 符号不同。
- \(\forall i\in [p+1,n-1]\)，\(|a_{i}|\leq|a_{i+1}|\)，且 \(a_{i+1}\) 和 \(a_i\) 符号不同。
启示我们按照绝对值大小填数。
设 \(f_{i,j\in \{0,1\},k\in \{0,1\}}\) 表示填完了绝对值 \(\geq i\) 的，目前最左边一个数符号是正还是负，最右边一个是正还是负。
考虑怎么转移。
我们将绝对值等于 \(i\) 的数拿出来，正负分开。
考虑枚举绝对值等于 \(i\) 的数中有 \(t\) 个要放在左边，剩下的放右边，贪心的去想肯定是把编号最小的放左边，编号大的放右边，所以在枚举 \(j\) 的情况下，其实放法是固定的。注意要求相邻两个数正负性不同，所以其实是正符号内部有序，负符号内部有序。
贡献可以树状数组简单计算。时间复杂度 \(O(n \log n)\)。
//code by Emissary
#include<bits/stdc++.h>
#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(ll x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(ll x){write(x), putchar(32);}
inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 5e5+5;
int n, a[MAXN], tree[3][MAXN], mu[2]={-1,1}, ans[MAXN];
int tot[2], k0, k1, le[MAXN], ri[MAXN], topf, stk[MAXN], uL[MAXN][2], uR[MAXN][2];
vc<int> col[2];
ll v1[MAXN], v2[MAXN];
ll dp[2][2], g[2][2];
struct NUM{
int v, col, id;
inline bool friend operator < (const NUM &x, const NUM &y){
return x.v>y.v;
}
}num[MAXN];
inline int lowbit(int x){return x & -x;}
inline void add(int x, int v, int t){
while(x<=n) tree[t][x]+=v, x+=lowbit(x);
return ;
}
inline int ask(int x, int t){
int s=0;
while(x) s+=tree[t][x], x^=lowbit(x);
return s;
}
inline int query(int l, int r, int t){return ask(r,t)-ask(l-1,t);}
inline void op(int l, int r){
memset(g,127/3,sizeof g);
col[0].clear(); col[1].clear();
for(int i=l;i<=r;++i) col[num[i].col].pb(num[i].id), add(num[i].id,-1,0);
for(int i=l;i<=r;++i){
le[num[i].id]=query(1,num[i].id-1,0);
ri[num[i].id]=query(num[i].id+1,n,0);
}
sort(col[0].begin(),col[0].end());
sort(col[1].begin(),col[1].end());
int L[2], R[2];
for(int i=0;i<2;++i){
for(int j=0;j<2;++j){
if(dp[i][j]>1ll*n*n) continue;
ll s=0; int now=i; L[0]=L[1]=0;
int len=col[0].size()+col[1].size();
for(int k=1;k<=len;++k) v1[k]=v2[k]=1e18;
for(int k=1;k<=len;++k){
if(L[now]==col[now].size()) break;
int c=col[now][L[now]]; L[now]++;
v1[k]=v1[k-1]+query(c+1,n,1); add(c,1,1); stk[++topf]=c;
now^=1; uL[k][0]=L[0], uL[k][1]=L[1];
}
while(topf) add(stk[topf],-1,1), --topf; now=j;
R[0]=(int)col[0].size()-1; R[1]=(int)col[1].size()-1;
uR[0][0]=R[0], uR[0][1]=R[1];
for(int k=1;k<=len;++k){
if(R[now]<0) break;
int c=col[now][R[now]]; R[now]--;
v2[k]=v2[k-1]+query(1,c-1,1); add(c,1,1); stk[++topf]=c;
now^=1; uR[k][0]=R[0], uR[k][1]=R[1];
}
while(topf) add(stk[topf],-1,1), --topf;
for(auto k:col[0]) s+=ri[k], add(k,1,1);
for(auto k:col[1]) s+=ri[k], add(k,1,1);
int A, B; now=i; L[0]=L[1]=0; ll S=0;
for(int k=0;k<=len;++k){
A=k&1, B=(len-k)&1;
if(uL[k][0]-1==uR[len-k][0] && uL[k][1]-1==uR[len-k][1]) g[i^A][j^B]=min(g[i^A][j^B],dp[i][j]+s+S+v1[k]+v2[len-k]);
if(k!=len){
if(L[now]==col[now].size()) break;
int c=col[now][L[now]]; L[now]++;
now^=1; S-=query(c+1,n,2); add(c,-1,1); S+=query(1,c-1,1); add(c,1,2); stk[++topf]=c; s+=le[c]-ri[c];
}
}
while(topf) add(stk[topf],-1,2), --topf;
while(L[0]<col[0].size()) add(col[0][L[0]],-1,1), L[0]++;
while(L[1]<col[1].size()) add(col[1][L[1]],-1,1), L[1]++;
}
}
for(int i=0;i<2;++i)
for(int j=0;j<2;++j) dp[i][j]=g[i][j];
return ;
}
signed main(){
n=read(); int c=0;
for(int i=1;i<=n;++i) a[i]=read()*mu[i%2], c+=a[i]==0;
for(int i=1;i<=n;++i){
if(a[i]<0) num[i].col=1;
else num[i].col=0; num[i].v=abs(a[i]); num[i].id=i;
}
sort(num+1,num+1+n);
int L, R, las;
if(n%2==0) L=R=1;
else L=1, R=0; las=1;
memset(dp,127/3,sizeof dp); dp[L][R]=0;
for(int i=1;i<=n;++i) add(i,1,0);
for(int i=2;i<=n-c;++i){
if(num[i].v!=num[i-1].v){
op(las,i-1);
las=i;
}
}
if(c!=n) op(las,n-c); ll ans=min(min(dp[0][0],dp[0][1]),min(dp[1][1],dp[1][0]));
eprint(ans>1ll*n*n?-1:ans);
return 0;
}