#include"bits/stdc++.h"
using namespace std;
#include "shoes.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
long long count_swaps(std::vector<int> s) {
int n = s.size();
int a[n];
int b[n];
queue<int> p[n + 1];
stack<int> p2[n + 1];
for (int i = 0 ; i < n ; i++) {
if (s[i] > 0) p[s[i]].push(i);
else p2[-s[i]].push(i);
}
int cnt = 0, cnt2 = 0;
for (int i = 0 ; i < n ; i++) {
if (s[i] < 0) {
a[i] = cnt++;
a[p[-s[i]].front()] = cnt++;
p[-s[i]].pop();
} else {
b[i] = cnt2 + 1;
b[p2[s[i]].top()] = cnt2;
cnt2 += 2;
p2[s[i]].pop();
}
}
// for (int i = 0 ; i < n ; i++) cout << b[i] << " ";
// cout << endl;
long long ret = 0;
long long ret2 = 0;
ordered_set<int> os, os2;
for (int i = 0 ; i < n ; i++) {
ret += os.order_of_key(-a[i]);
os.insert(-a[i]);
}
for (int i = n - 1 ; i >= 0 ; i--) {
ret2 += os2.order_of_key(b[i]);
os2.insert(b[i]);
}
return min(ret, ret2);
}
