#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
map<int, queue<int> > rgt;
int LSO( int n ){ return ( n&(-n) ); }
class FT{
private: vector<int> ft;
public:
FT( int n ){ ft.assign(n+1, 0); }
int rsq(int b){
int sum = 0;
for( ; b; b -= LSO(b) ){ sum += ft[b];}
return sum;
}
void adjust( int k, int v ){ for(; k < (int)ft.size(); k += LSO(k) ){ ft[k]+=v; } }
//void report(){ for( int i = 0; i < ft.size(); i++ ){ cout << ft[i] << " "; } cout << endl; }
};
long long count_swaps(vector<int> s) {
//num
ll S = s.size();
FT tre = FT(S);
//iterate through s -- preprocess
for( int i = 0; i < S; i++ ){
rgt[ s[i] ].push(i+1);
tre.adjust( i+1, 1 );
}
bool idim[S+2];
memset( idim, true, sizeof idim );
//process
ll grand = 0;
for( int i = 0; i < S; i++ ){
if( idim[i+1] ){
idim[i+1] = false;
rgt[ s[i] ].pop();
tre.adjust( i+1, -1 );
//move partner
ll val = rgt[ -s[i] ].front();
//for( int j = 0; j < val; j++ ){ grand += idim[j]; }
grand += tre.rsq(val-1);
idim[val] = false;
rgt[ -s[i] ].pop();
tre.adjust( val, -1);
if( s[i] > 0 ){ grand++; }
}
}
return grand;
}
