#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
class SegmentTree {
private:
ll n;
vi st,data;
ll left(ll x){ return (x << 1); }
ll right(ll x){ return ((x << 1) + 1); }
void build (ll i, ll l, ll r){
if (l == r){
st[i] = data[l];
}else{
ll m = (l+r)/2;
build (left(i),l,m);
build (right(i),m+1,r);
}
}
ll query (ll i, ll l, ll r, ll ql, ll qr){
if (qr >= r && l >= ql){
return st[i];
}else if (ql > r || l > qr){
return 0;
}else{
ll m = (l+r)/2;
ll ans = 0;
ans += query(left(i),l,m,ql,qr);
ans += query(right(i),m+1,r,ql,qr);
return ans;
}
}
void update (ll i, ll l, ll r, ll idx, ll dx){
if (r >= idx && idx >= l){
if (r == l){
st[i] += dx;
}else{
ll m = (l+r)/2;
update(left(i),l,m,idx,dx);
update(right(i),m+1,r,idx,dx);
st[i] = st[left(i)] + st[right(i)];
}
}
}
public:
SegmentTree (const vi& _data): data(_data){
n = data.size();
st.resize(4*n);
}
ll query (ll l, ll r){
return query(1,0,n-1,l,r);
}
ll update (ll idx, ll dx){
update(1,0,n-1,idx,dx);
}
};
class LinkedList {
private:
ll n; vi nxt,prv;
public:
LinkedList(const ll& _n): n(_n){
nxt.assign(n,-1); prv.assign(n,-1);
for (ll i = 0; n > i; i++){
if (i != n-1) nxt[i] = i+1;
if (i != 0) prv[i] = i-1;
}
}
void rmv (ll idx){
if (nxt[idx] != -1){
prv[nxt[idx]] = prv[idx];
}
if (prv[idx] != -1){
nxt[prv[idx]] = nxt[idx];
}
}
ll get_nxt (ll idx){
return nxt[idx];
}
};
map<ll,set<ll> > byVals;
long long count_swaps(vector<int> s) {
ll n;
n = s.size(); n /= 2;
ll ans = 0;
SegmentTree st(vi(2*n,0));
set<ll> available;
for (ll i = 0; 2*n > i; i++){
if (byVals.find(s[i]) == byVals.end()) byVals[s[i]] = set<ll>() ;
byVals[s[i]].insert(i);
available.insert(i);
}
for (ll i = 0; n > i; i++){
ll ptr = *available.begin();
ll ptr2 = *byVals[-s[ptr]].begin();
ll modptr = st.query(0,ptr)+ptr;
ll modptr2 = st.query(0,ptr2)+ptr2;
ans += modptr2-1;
if (s[ptr] > 0) ans++;
//cout << ptr << ' ' << ptr2 << ' ' << modptr << ' ' << modptr2 << endl;
available.erase(ptr);
available.erase(ptr2);
byVals[s[ptr]].erase(ptr);
byVals[s[ptr2]].erase(ptr2);
st.update(ptr,-1);
st.update(ptr2,-1);
}
return ans;
}
