#include "bits/stdc++.h"
#include "shoes.h"
using namespace std;
struct node {
int segment_left, segment_right, segment_middle;
int value;
node *left, *right;
node(int sle, int sri) {
// cout << sle << ' ' << sri << endl;
this->segment_left = sle;
this->segment_right = sri;
int mid = (sle + sri) / 2;
this->segment_middle = mid;
this->value = 0;
if (sle == sri) return;
left = new node(sle, mid);
right = new node(mid+1, sri);
}
void update(int pos, int va) {
if (pos < segment_left) return;
if (pos > segment_right) return;
if (pos == segment_left && pos == segment_right) {
value = va;
return;
}
if (pos <= segment_middle) {
left->update(pos, va);
}
else {
right->update(pos, va);
}
value = left->value + right->value;
}
int qry(int a, int b) {
if (b < segment_left || a > segment_right) {
return 0;
}
if (a <= segment_left && b >= segment_right) {
return value;
}
return left->qry(a, b) + right->qry(a, b);
}
} *root;
void setup(int n) {
root = new node(0, n-1);
}
void update(int ind, int val) {
root->update(ind, val);
}
int query(int a, int b) {
return root->qry(a, b);
}
long long count_swaps(vector<int> s) {
long long need = 0;
set<pair<int, int> > opn; // value, index
int n = s.size();
vector<pair<int, int> > vc;
for (int i=0; i<n; i++) {
int wh = s[i];
int sea = -wh;
set<pair<int, int> >::iterator x = opn.lower_bound(make_pair(sea, INT_MIN));
if (x != opn.end() && x->first == sea) {
int other = x->second;
vc.push_back(make_pair(other, i));
opn.erase(x);
}
else {
opn.insert(make_pair(wh, i));
}
}
sort(vc.begin(), vc.end());
setup(n);
for (int i=0; i<vc.size(); i++) {
// cout << vc[i].first << ' ' << vc[i].second << endl;
long long aft = s[vc[i].second];
long long bef = s[vc[i].first];
if (aft < bef) {
// cout << " sw" << endl;
need++;
}
long long dist = vc[i].second - vc[i].first - 1;
// cout << " > " << dist << endl;
dist -= query(vc[i].first, vc[i].second);
// cout << " : " << dist << endl;
update(vc[i].first, 1);
update(vc[i].second, 1);
need += dist;
}
return need;
}
