#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
map<int , vector<int> >num;
vector<pair<int , int> >erg;
int vis[200000] , pref[200000], seg[800000], lazy[800000];
void pro(int id , int l , int r){
seg[id] += lazy[id];
if(l != r){
lazy[id * 2] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
}
lazy[id] = 0;
}
int up(int id , int l , int r, int gewl , int gewr , int gew){
if(gewr < gewl){
return 0;
}
pro(id , l , r);
if(l > gewr || gewl > r){
return 0;
}
else if(gewl <= l && r <= gewr){
// cout << l << ' ' << r <<' ' << id << "\n";
seg[id] += gew;
if(l != r){
lazy[id * 2] += gew;
lazy[id * 2 + 1] += gew;
}
return gew;
}
int m = (l + r)/2 , cmp;
cmp = up(id * 2 , l , m , gewl , gewr , gew) | up(id * 2 + 1 , m + 1 , r , gewl , gewr , gew);
seg[id] += cmp;
return cmp;
}
long long count_swaps(vector<int> s) {
long long menge = s.size() , be , en , re = 0 , len;
for(len = 1 ; len < menge ; len *= 2);
for(int i = menge - 1 ; i >= 0 ; i--){
num[s[i]].push_back(i);
}
for(int i = 0 ; i < menge ; i++){
if(vis[i] == 1){
continue;
}
be = i;
en = num[s[i] * -1][num[s[i] * -1].size() - 1];
num[s[i] * -1].pop_back();
num[s[i]].pop_back();
// if(be > en){
// swap(be , en);
// }
up(1 , 1 , len , be + 2 , en , 1);
up(1 , 1 , len , be + 1 , be + 1 , 0);
up(1 , 1 , len , en + 1 , en + 1, 0);
vis[be] = 1;
vis[en] = 1;
// cout << be << ' ' << en << "\n\n";
be += seg[be + len];
en += seg[en + len];
// cout << be << ' ' << en << "\n\n";
if(s[i] > 0){
re++;
}
re += (en - be - 1);
}
return re;
}
