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;}
struct Fen{
int n;
vector<int>tree;
void basla(int N){
n=N;
tree.resize(n,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;
void ekle(int i){
if(!son[0][i].size())return;
st.insert({fen.query(son[0][i].back()-1)+fen.query(son[1][i].back()-1)-(son[0][i].back()<son[1][i].back()?1:0),i});
}
ll count_swaps(vector<int>s) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
n=s.size();
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++){
pair<int,int>p=*st.begin();
st.erase(st.begin());
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;
}
