typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "shoes.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
#define int ll
struct Fen{
int n;
vector<int>tree;
void basla(int N){
n=N;
tree.resize(n+1,0);
return;
}
void update(int tar,int x){
while(tar<=n){
tree[tar]+=x;
tar+=(tar&-tar);
}
}
int query(int tar){
int res=0;
while(tar){
res+=tree[tar];
tar-=(tar&-tar);
}
return res;
}
};
ll n;
int arr[200001];
set<pair<int,int>>st;
vector<int>son[2][100001];
Fen fen;
vector<int32_t>S;
void ekle(int i){
if(!son[0][i].size())return;
st.insert({/*cal(i)*/0,i});
}
ll cal(int i){
return fen.query(son[0][i].back()-1)+fen.query(son[1][i].back()-1)-(son[0][i].back()<son[1][i].back()?1:0);
}
int bf(vector<int>cur){
if(ll(cur.size())==n){
for(int i=0;i<n;i+=2){
if(S[cur[i]]>0||(S[cur[i+1]]+S[cur[i]])!=0)
return sonsuz;
}
Fen yem;yem.basla(n);
for(int i=1;i<=n;i++){
yem.update(i,1);
}
int res=0;
for(int i=0;i<n;i++){
res+=yem.query(cur[i]);
yem.update(cur[i]+1,-1);
}
return res;
}
set<int>yok;
for(int i=0;i<n;i++){
yok.insert(i);
}
for(int x:cur){
yok.erase(x);
}
int res=sonsuz;
for(int x:yok){
cur.pb(x);
res=min(res,bf(cur));
cur.pop_back();
}
return res;
}
ll count_swaps(vector<int32_t>s) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
n=s.size();
S=s;
if(n<=8){
return bf({});
}
bool peynir=true;
for(int i=0;i*2<n;i++){
if(s[i]>0||(s[i]+s[i+(n/2)])!=0){
peynir=false;
break;
}
}
if(peynir)return ((n/2)*((n/2)-1))/2;
fen.basla(n);
for(int i=1;i<=n;i++){
arr[i]=s[i-1];
fen.update(i,1);
son[arr[i]<0?0:1][abs(arr[i])].pb(i);
}
for(int i=1;(i<<1)<=n;i++){
reverse(son[0][i].begin(),son[0][i].end());
reverse(son[1][i].begin(),son[1][i].end());
ekle(i);
}
ll ans=0;
for(int i=0;i*2<n;i++){
ll mx=st.begin()->fr,pos=st.begin()->sc;
for(pair<int,int>x:st){
ll cur=cal(x.sc);
if(cur>mx){
mx=cur;
pos=x.sc;
}
}
pair<int,int>p={mx,pos};
st.erase({0,pos});
int lef=son[0][p.sc].back();
int rig=son[1][p.sc].back();
son[0][p.sc].pop_back();
son[1][p.sc].pop_back();
fen.update(lef,-1);
fen.update(rig,-1);
ekle(p.sc);
ans+=p.fr;
}
return ans;
}
