#include "shoes.h"
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
constexpr int clog2(int n) { return ((n < 2) ? 1 : 1 + clog2(n / 2)); }
template<typename T, typename Merge>
class SegmentTree
{
public:
SegmentTree(Merge m)
:merge(m) {}
void init(vector<T>& raw_)
{
raw = raw_;
n = (int)raw.size();
int sz = (1 << (clog2(n) + 1));
data.resize(sz);
_init(raw, 1, 0, n - 1);
}
T modify(int idx, function<T(T)> modifier) { return update(idx, modifier(raw[idx])); }
T update(int idx, const T& newVal) { raw[idx] = newVal; return _update(1, 0, n - 1, idx, newVal); }
T query(int left, int right) { return _query(1, 0, n - 1, left, right); }
private:
vector<T> raw;
vector<T> data;
int n;
Merge merge;
T _init(vector<T>& raw, int node, int start, int end)
{
int mid = (start + end) / 2;
if (start == end)
return data[node] = raw[start];
else
return data[node] = merge(_init(raw, node * 2, start, mid),
_init(raw, node * 2 + 1, mid + 1, end));
}
T _update(int node, int start, int end, int index, const T& newVal)
{
if (index < start || index > end)
return data[node];
if (start == end)
data[node] = newVal;
else
{
int mid = (start + end) / 2;
data[node] = merge(_update(node * 2, start, mid, index, newVal),
_update(node * 2 + 1, mid + 1, end, index, newVal));
}
return data[node];
}
T _query(int node, int start, int end, int left, int right)
{
if (left <= start && end <= right)
return data[node];
int mid = (start + end) / 2;
if (mid < left)
return _query(node * 2 + 1, mid + 1, end, left, right);
if (mid + 1 > right)
return _query(node * 2, start, mid, left, right);
return merge(_query(node * 2, start, mid, left, right),
_query(node * 2 + 1, mid + 1, end, left, right));
}
};
template<typename T, typename Merge>
SegmentTree<T, Merge> segTree(Merge merge)
{
return SegmentTree<T, Merge>(merge);
}
set<int> mi[100005];
set<int> pl[100005];
long long count_swaps(vector<int> s) {
vector<bool> used(s.size(), false);
long long ans = 0;
vector<int> raw(s.size(), 1);
auto tree = segTree<int>([](const int& l, const int& r) { return l + r; });
tree.init(raw);
for (int i = 0; i < s.size(); i++)
{
if (s[i] > 0)
pl[s[i]].insert(i);
else
mi[-s[i]].insert(i);
}
for (int i = 0; i < s.size(); i++)
{
if (used[i])
continue;
if (s[i] > 0)
{
int near = *mi[s[i]].lower_bound(i);
mi[s[i]].erase(near);
used[near] = true;
ans += tree.query(0, near) - tree.query(0, i);
tree.update(near, 0);
}
else
{
int near = *pl[-s[i]].lower_bound(i);
pl[-s[i]].erase(near);
used[near] = true;
ans += tree.query(0, near) - tree.query(0, i) - 1;
tree.update(near, 0);
}
}
return ans;
}
