#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int nax = 1e5 + 3;
struct bit {
int a[nax] = {0};
void add(int i) {
while(i<nax) {
++a[i];
i += i&-i;
}
}
int query(int i) {
int ret = 0;
while(i>0) {
ret += a[i];
i -= i&-i;
}
return ret;
}
int query(int l, int r) {
if(l==0) return query(r);
return query(r) - query(l-1);
}
} b;
long long count_swaps(vector<int> s) {
int n = s.size();
set<pair<int,int>>by_index, by_color;
for(int i=0; i<n; ++i) {
by_index.insert(make_pair(i, s[i]));
by_color.insert(make_pair(s[i], i));
}
long long ans = 0;
int cur_index = 0;
while(!by_index.empty()) {
auto x = *by_index.begin();
by_index.erase(x);
by_color.erase(make_pair(x.second, x.first));
auto y = *by_color.lower_bound(make_pair(-x.second, -1));
by_color.erase(y);
by_index.erase(make_pair(y.second, y.first));
if(x.second>0) ++ans;
//find real index of y.second
int inc = b.query(y.second, n);
int real_index = y.second + inc;
ans += real_index - cur_index - 1;
b.add(y.second);
cur_index += 2;
}
return ans;
}
