#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int st[400000];
void update(int cur, int lo, int hi, int l, int r, int val)
{
if ((r < lo) || (l > hi))
{
return;
}
if(( lo >= l ) && ( hi <= r))
{
st[cur] +=val;
return;
}
int mid = (lo + hi) / 2;
update(2 * cur, lo, mid, l , r, val);
update(2 * cur + 1, mid + 1, hi, l, r, val);
}
int query(int cur, int lo, int hi, int idx)
{
if (lo == hi)
{
return st[cur];
}
int mid = (lo + hi) / 2;
if( idx <= mid)
{
return st[cur] + query( 2 * cur, lo, mid, idx);
}
else
{
return st[cur] + query( 2 * cur + 1, mid + 1, hi, idx);
}
}
long long count_swaps(vector<int> s) {
int n = s.size();
vector<deque<int>> szidx( 2 * n + 1);
vector<bool> there(n + 1, 1);
for(int i = 1; i <= n; i ++)
{
int val = s[i-1];
szidx[val + n].push_back(i);
}
/*
for(auto sz: szidx)
{
for (auto a : sz)
{
cout << a << " ";
}
cout << '\n';
}
cout << '\n';
*/
ll ans = 0;
vector<int> sorted;
for(int i = 1; i <=n; i ++)
{
if(there[i])
{
int pair = szidx[(0-s[i-1]) + n].front();
szidx[(0-s[i-1]) + n].pop_front();
szidx[s[i-1] + n].pop_front();
ans += pair + (query(1,1,n,pair)) - (i + query(1,1,n,i)) - 1;
cout << i << " " << pair << " : " <<pair + (query(1,1,n,pair)) - (i + query(1,1,n,i)) - 1 << '\n';
there[pair] = false;
sorted.push_back(s[i-1]);
sorted.push_back(s[pair-1]);
update(1,1,n, i, pair, 1 );
}
}
for(int i = 0; i < n; i +=2)
{
if(sorted[i] > 0)
{
ans +=1;
}
}
return ans;
}
