// Source: https://oj.uz/problem/view/IOI19_shoes
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define FOR(i, a, b) for (int i = (a); i<b; i++)
bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }
bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }
const int N = 2e5 + 10;
struct BIT {
private:
int sz;
vi bit;
public:
BIT(int n) : sz(n), bit(n + 1) {}
void add(int pos, int val) {
pos++;
for (; pos <= sz; pos += (pos & -pos)) {
bit[pos] += val;
}
}
int pref(int ind) {
ind++;
int res = 0;
for (; ind > 0; ind -= (ind & -ind)) res += bit[ind];
return res;
}
};
queue<int> l[N], r[N];
BIT bit(N);
ll count_swaps(vi s) {
int n = s.size();
FOR(i, 0, n) {
if (s[i] < 0) l[-s[i]].push(i);
else r[s[i]].push(i);
bit.add(i, 1);
}
ll ans = 0;
FOR(i, 0, n) {
if (s[i] != 0) {
int nxt;
if (s[i] > 0) {
nxt = l[s[i]].front();
ans++;
} else {
nxt = r[-s[i]].front();
s[i] = -s[i];
}
r[s[i]].pop();
l[s[i]].pop();
bit.add(i, -1);
s[i] = 0;
s[nxt] = 0;
bit.add(nxt, -1);
ans += bit.pref(nxt);
}
}
return ans;
}
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout << count_swaps({2, 1, -1, -2}) << endl;
// }
