#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
// inline void setup()
// {
// #ifndef ONLINE_JUDGE
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// #endif
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// }
class FENWICK_TREE
{
private:
int tree_size;
vector<int> tree;
public:
FENWICK_TREE(int new_size)
{
tree_size = new_size;
tree.resize(tree_size + 1, 0);
}
void Update(int pos, int val)
{
while (pos <= tree_size)
{
tree[pos] += val;
pos += pos & (~(pos - 1));
}
}
int Get(int pos)
{
int res = 0;
while (0 < pos)
{
res += tree[pos];
pos -= pos & (~(pos - 1));
}
return res;
}
};
long long count_swaps(vector<int> S)
{
int a, b, c, d;
vector<int> v;
set<int> p;
long long res = 0;
queue<int> neg[S.size() / 2 + 1], pos[S.size() / 2 + 1];
FENWICK_TREE ft(S.size());
S.insert(S.begin(), 0);
for (int i = 1; i < S.size(); ++i)
{
if (S[i] < 0)
{
neg[-S[i]].push(i);
p.insert(i);
}
else
{
pos[S[i]].push(i);
}
}
for (int i = 1, j = 1; i < S.size(); ++i)
{
while (j < S.size() && S[j] == 0)
{
j++;
}
if (!(i & 1))
{
if (-v.back() == S[j])
{
v.push_back(S[j]);
j++;
continue;
}
a = pos[-v.back()].front();
res += a - j - (ft.Get(a) - ft.Get(j - 1));
ft.Update(a, 1);
pos[-v.back()].pop();
v.push_back(S[a]);
S[a] = 0;
}
else
{
if (S[j] < 0)
{
neg[-S[j]].pop();
v.push_back(S[j]);
p.erase(j);
j++;
continue;
}
a = *p.begin();
res += a - j - (ft.Get(a) - ft.Get(j - 1));
ft.Update(a, 1);
neg[S[a]].pop();
p.erase(a);
v.push_back(S[a]);
S[a] = 0;
}
}
return res;
}
// int main()
// {
// setup();
// int n;
// vector<int> v;
// cin >> n;
// v.resize(n);
// for (int i = 0; i < n; ++i)
// {
// cin >> v[i];
// }
// cout << count_swap(v);
// return 0;
// }
