#include "shoes.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int MAX = 200007;
struct BIT {
int T[MAX];
void Update(int i, int v) {
for (i += 3; i < MAX; i += i & -i) T[i] += v;
}
int Query(int L, int R) {
int ret = 0; L--;
for (L += 3; R; R -= R & -R) ret += T[R];
for (R += 3; L; L -= L & -L) ret -= T[L];
return ret;
}
} T;
ll count_swaps(vector<int> S) {
int N = S.size();
map<int, vector<int>> C;
for (int i = 0; i < N; ++i) C[S[i]].push_back(i);
for (auto& [_, v] : C) reverse(v.begin(), v.end());
ll ret = 0;
vector<pii> P;
for (int i = 0; i < N; ++i) {
if (C[S[i]].empty() || C[S[i]].back() != i) continue;
int t = C[-S[i]].back(); C[-S[i]].pop_back();
P.emplace_back(i, t);
if (0 < S[i]) ret++;
}
for (auto [a, b] : P) {
ret += (b - a) - T.Query(a, b);
T.Update(b, 1);
}
return ret;
}
