#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long int lli;
const int MAXN = 200010;
class FenwickTree
{
public:
void update(int i, int v)
{
for( ; i < MAXN ; i += i & -i )
BIT[i] += v;
}
int query(int i)
{
int ans = 0;
for( ; i > 0 ; i -= i & -i )
ans += BIT[i];
return ans;
}
int sum(int L, int R) { return query( R ) - query( L - 1 ); }
FenwickTree() { memset( BIT , 0 , sizeof(BIT) ); }
private:
int BIT[MAXN];
};
int last[MAXN];
vector< int > L[MAXN];
vector< int > R[MAXN];
bool marc[MAXN];
FenwickTree BIT;
long long count_swaps(vector<int> s)
{
int n = s.size();
for(int i = 1 ; i <= n ; i++)
{
int val = abs( s[i - 1] );
if( s[i - 1] < 0 ) L[ val ].push_back( i );
else R[ val ].push_back( i );
}
for(int i = 1 ; i <= n ; i++)
BIT.update( i , 1 );
lli ans = 0;
for(int i = 1 ; i <= n ; i++)
{
if( marc[i] ) continue;
int val = abs( s[i - 1] );
if( s[i - 1] > 0 )
{
ans++;
swap( L[val][ last[val] ] , R[val][ last[val] ] );
}
marc[ R[val][ last[val] ] ] = true;
ans += BIT.sum( L[val][ last[val] ] + 1 , R[val][ last[val] ] ) - 1;
BIT.update( R[val][ last[val] ] , -1 );
last[val]++;
}
return ans;
}
