#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];
};
vector< int > L;
vector< int > R;
bool marc[MAXN];
FenwickTree BIT;
long long count_swaps(vector<int> s)
{
int n = s.size();
for(int i = 1 ; i <= n ; i++)
{
if( s[i - 1] < 0 ) L.push_back( i );
else R.push_back( i );
}
for(int i = 1 ; i <= n ; i++)
BIT.update( i , 1 );
lli ans = 0;
int last = 0;
for(int i = 1 ; i <= n ; i++)
{
if( marc[i] ) continue;
if( s[i - 1] > 0 )
{
ans++;
swap( L[last] , R[last] );
}
marc[ R[last] ] = true;
ans += BIT.sum( L[last] + 1 , R[last] ) - 1;
BIT.update( R[last] , -1 );
last++;
}
return ans;
}
