// Dmitry _kun_ Sayutin (2019)
#include <bits/stdc++.h>
#include "shoes.h"
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::tuple;
using std::make_tuple;
using std::get;
using std::min;
using std::abs;
using std::max;
using std::swap;
using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;
#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif
#define SZ(vec) int((vec).size())
#define ALL(data) data.begin(),data.end()
#define RALL(data) data.rbegin(),data.rend()
#define TYPEMAX(type) std::numeric_limits<type>::max()
#define TYPEMIN(type) std::numeric_limits<type>::min()
vector<int> change(vector<int> v) {
int n = (int)v.size() / 2;
vector<int> cnt(n, 0);
for(int i = 0; i < 2*n; i++)
if(v[i] > 0)
cnt[v[i] - 1]++;
for(int i = 1; i < n; i++)
cnt[i] += cnt[i-1];
vector<int> cntl = cnt, cntr = cnt;
for(int i = 0; i < 2*n; i++)
if(v[i] > 0)
v[i] = (--cntr[v[i] - 1]) + 1;
else
v[i] = -((--cntl[-v[i] - 1]) + 1);
return v;
}
long long count_swaps(vector<int> s) {
s = change(s);
vector<pair<int, bool>> in(SZ(s));
vector<int> where(SZ(s) / 2, -1);
for (int i = 0; i != SZ(s); ++i) {
in[i].first = abs(s[i]) - 1;
in[i].second = (s[i] < 0 ? 0 : 1);
if (where[in[i].first] == -1)
where[in[i].first] = i;
}
vector<int> fenw(SZ(in));
for (int i = 0; i != SZ(in); ++i)
fenw[i] = 1 + i - (i & (i+1));
long long ans = 0;
vector<char> dead(SZ(in), false);
for (int pos = SZ(in) - 1; pos >= 0; --pos)
if (not dead[pos]) {
dead[pos] = 1;
int i = where[in[pos].first];
dead[i] = 1;
int dist = 0;
for (int p = pos; p >= 0; p = (p & (p + 1)) - 1)
dist += fenw[p];
for (int p = i; p >= 0; p = (p & (p + 1)) - 1)
dist -= fenw[p];
if (in[pos].second == 1)
--dist;
ans += dist;
for (int p = i; p < SZ(fenw); p = p | (p + 1))
fenw[p] -= 1;
}
return ans;
}
