#include <bits/stdc++.h>
#include "shoes.h"
#define rep(i,n) for(int i = 0; i < n; i++)
#define ll long long
#define ss second
#define ff first
using namespace std;
int wiel = 1024*512-1;
ll drzewo[1024*512-1];
int n;
void add_t(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return;
if(p1 >= s1 && p2 <= s2)
{
drzewo[akt-1]++;
return;
}
add_t(akt*2,p1,(p1+p2)/2,s1,s2);
add_t(akt*2+1,(p1+p2)/2+1,p2,s1,s2);
}
int query_t(int akt)
{
int wyn = drzewo[akt-1];
if(akt != 1) wyn += query_t(akt/2);
return wyn;
}
long long count_swaps(vector<int> s)
{
ll ans = 0;
n = (int)s.size();
set<pair<int,int>> se;
rep(i,n)
{
se.insert({s[i],i});
}
//se.erase({s[0],0});
rep(i,n)
{
if(se.find({s[i],i}) == se.end()) continue;
//cout << i << " i\n";
set<pair<int,int>>::iterator t_ = se.lower_bound({-s[i],-1});
pair<int,int> t = *t_;
//cout << t.ff << " " << t.ss << " t\n";
se.erase(se.find({t.ff,t.ss}));
se.erase(se.find({s[i],i}));
ll odl1 = query_t(wiel/2+1+i);
ll odl2 = query_t(wiel/2+1+t.ss);
add_t(1,0,wiel/2,t.ss,wiel/2);
//cout << odl1 << " " << odl2 << " odl\n";
if(s[i] < 0)
{
ans += -(odl2-odl1) + t.ss - i -1;
}
else
{
ans +=-(odl2-odl1) + t.ss - i;
}
//cout << ans << "\n\n";
}
return ans;
}
