#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int drz[2 * N];
vector<int> pos[N][2];
int tab[N];
bool vis[N];
inline int A(int x)
{
if(x < 0) return -x;
return x;
}
void Add(int v)
{
v += N;
while(v > 0)
{++drz[v]; v /= 2;}
}
int Query(int a, int b)
{
a += N - 1; b += N + 1;
int s = 0;
while(a / 2 != b / 2)
{
if(a % 2 == 0) s += drz[a + 1];
if(b % 2 == 1) s += drz[b - 1];
a /= 2; b /= 2;
}
return s;
}
long long count_swaps(vector<int> s)
{
int n = s.size();
ll ans = 0LL;
for(int i = 0; i < n; ++i)
{
tab[i + 1] = s[i];
pos[A(s[i])][(s[i] < 0)].pb(i + 1);
}
for(int i = 1; i <= n; ++i)
for(int j = 0; j < 2; ++j)
reverse(pos[i][j].begin(), pos[i][j].end());
for(int i = 1; i <= n; ++i)
{
if(vis[i]) continue;
int r = (tab[i] < 0), x = A(tab[i]);
int j = pos[x][r ^ 1].back();
//cerr << "swp i: " << i << " " << tab[i] << " j: " << j << " " << ans << "\n";
pos[x][0].pop_back(); pos[x][1].pop_back();
ans += (ll)(j - i - 1);
ans += (ll)Query(j, n) - (ll)Query(i, n);
Add(j);
vis[j] = true;
if(r == 0) ++ans;
}
return ans;
}
