#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
struct SeggsTree{
SeggsTree *l = 0, *r = 0;
int low, high;
struct Data{
int value;
Data() {value = 0;}
Data(int v) {value = v;}
void update(int a) {value += a;}
static Data merge(Data a, Data b){return Data(a.value + b.value);}
};
Data d;
SeggsTree(vector<int> &arr, int L, int R){
low = L, high = R;
if(R-L <= 1){
d = Data(arr[L]);
return;
}
int mid = (high + low) / 2;
l = new SeggsTree(arr, L, mid);
r = new SeggsTree(arr, mid, R);
d = Data::merge(l->d, r->d);
}
~SeggsTree(){
if(!l) return;
delete l;
delete r;
}
int lazy = 0;
void push(){
if(lazy == 0) return;
if(!l) return;
l->d.update(lazy);
l->lazy = lazy;
r->d.update(lazy);
r->lazy = lazy;
lazy = 0;
}
Data query(int L, int R){
if(R <= low || high <= L) return Data(0);
if(L <= low && high <= R) return d;
push();
return Data::merge(l->query(L, R), r->query(L, R));
}
void update(int v, int L, int R){
if(R <= low || high <= L) return;
if(L <= low && high <= R){
d.update(v);
lazy += v;
return;
}
push();
l->update(v, L, R);
r->update(v, L, R);
d = Data::merge(l->d, r->d);
}
};
ll count_swaps(vector<int> S){
int n = S.size() / 2;
if(n == 1){
if(S[0] < 0) return 0;
return 1;
}
vector<int> left(n);
vector<int> right(n);
int l = 0;
int r = 0;
for(int i = 0; i < n*2; i++){
if(S[i] < 0){
left[l] = i;
l++;
}else{
right[r] = i;
r++;
}
}
SeggsTree *lTree = new SeggsTree(left, 0, n);
SeggsTree *rTree = new SeggsTree(right, 0, n);
ll swaps = 0;
// for(int i = 0; i < n; i++){
// cout << left[i] << ' ';
// }
// cout << '\n';
// for(int i = 0; i < n; i++){
// cout << right[i] << ' ';
// }
// cout << '\n';
for(int i = 0; i < n*2; i++){
// cout << '\n';
if(i%2==0){
//left
int p = lTree->query(i/2, i/2+1).value;
swaps += p - i;
int low = 0;
int high = n+1;
while(high - low > 1){
int mid = (high + low) / 2;
if(rTree->query(mid-1, mid).value > p) high = mid;
else low = mid;
}
// cout << low << '\n';
if(low > 0) rTree->update(1, i/2, low);
// for(int i = 0; i < n; i++){
// cout << rTree->query(i, i+1).value << ' ';
// }
// cout << '\n';
}else{
int p = rTree->query(i/2, i/2+1).value;
swaps += p - i;
int low = 0;
int high = n+1;
while(high - low > 1){
int mid = (high + low) / 2;
if(lTree->query(mid-1, mid).value > p) high = mid;
else low = mid;
}
// cout << low << '\n';
if(low > 0) lTree->update(1, i/2, low);
// for(int i = 0; i < n; i++){
// cout << lTree->query(i, i+1).value << ' ';
// }
// cout << '\n';
}
// cout << i << ": " << swaps << '\n' << '\n';
}
return swaps;
}
// int main(){
// cout << count_swaps({-2, -2, -2, 2, 2, 2});
// return 0;
// }
