#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include "shoes.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF 100000000000000000LL
int insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
class ST
{
public:
ll N; vector<ll> ar; vector<ll> p;
ll neut;
ll op(ll a, ll b)
{
return (a+b);
}
ST(vector<ll> arr)
{
neut=0;
N = (ll) 1<<(ll) ceil(log2(arr.size()));
REP(i,0,arr.size()) {ar.pb(arr[i]);}
REP(i,arr.size(),N) {ar.pb(neut);}
REP(i,0,N) {p.pb(0);}
REP(i,0,N) {p.pb(ar[i]);}
ll cur = N-1;
while(cur>0)
{
p[cur]=op(p[2*cur],p[2*cur+1]);
cur--;
}
}
ll query(ll a,ll b, ll c, ll x, ll y) //c=current node, starting in 1, a,b=range of query, x,y=range of node c in the array down, x,y from 0 to N-1. query(a,b)->query(a,b,1,0,N-1)
{
if(y<a || x>b) {return neut;}
if(x>=a && y<=b) {return p[c];}
ll mid=(x+y)/2;
return op(query(a,b,2*c,x,mid),query(a,b,2*c+1,mid+1,y));
}
void update(ll s, ll a, ll c, ll x, ll y) //positions in [a,b] from 0 to N-1 gets +s
{
if(y<a || x>a) {return ;}
p[c]+=s;
if(c==a+N) {ar[a]+=s; return;}
ll mid=(x+y)/2;
update(s,a,2*c,x,mid); update(s,a,2*c+1,mid+1,y);
}
};
ll count_swaps(vector<int> s)
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll N=s.size()/2;
map<ll,vector<ll> > m;
vector<ll> xx;
REP(i,0,2*N)
{
if(m.find(s[i])==m.end()) {m[s[i]]=xx;}
m[s[i]].pb(i);
}
ll ind=0; ll ans=0;
REP(i,0,2*N)
{
if(m.find(i)==m.end()) {continue;}
REP(j,0,m[i].size())
{
if(m[i][j]<m[-i][j]) {ans++;}
s[m[i][j]]=ind;
s[m[-i][j]]=ind;
ind++;
}
}
map<ll,ll> t;
ind=0;
REP(i,0,2*N)
{
if(t.find(s[i])==t.end()) {t[s[i]]=ind; ind++;}
}
REP(i,0,2*N) {s[i]=t[s[i]];}
vector<ll> x; REP(i,0,N) {x.pb(0LL);}
ST S(x);
REP(i,0,2*N)
{
ans+=S.query(s[i]+1,S.N-1,1,0,S.N-1);
S.update(1,s[i],1,0,S.N-1);
}
return ans;
}
