#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 18;
int n, seg[b * 2], li, ri, l, r, n2;
queue<int> q[b];
int find(){
int ix = 1;
while(ix < b){
ix <<= 1;
if(!seg[ix]) ix++;
}
return ix - b;
}
void upd(int ix){
ix += b;
while(ix) {
seg[ix]--;
ix /= 2;
}
}
int sum(int l, int r){
l += b; r += b;
int ret = 0;
while(l <= r){
if(l & 1) ret += seg[l++];
if(!(r & 1)) ret += seg[r--];
l /= 2; r /= 2;
}
return ret;
}
ll count_swaps(vector<int> v){
ll ans = 0; n = v.size(); n2 = n / 2;
for(int i = 0; i < n; i++) {
if(v[i] < 0) v[i] = -v[i];
else v[i] = v[i] + n2;
q[v[i]].emplace(i);
seg[b + i] = 1;
}
for(int i = b - 1; i; i--) seg[i] = seg[i * 2] + seg[i * 2 + 1];
for(int i = 0; i < n2; i++){
li = find(); upd(li);
l = v[li];
q[l].pop();
r = l > n2 ? l - n2 : l + n2;
ri = q[r].front(); upd(ri);
q[r].pop();
ans += sum(0, ri) + (l > n2);
}
return ans;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> v(n);
for(int& x : v) cin >> x;
cout << count_swaps(v);
return 0;
}
*/
/*
test1
4
2 1 -1 -2
test2
6
-2 2 -2 2 -2 2
*/
