#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 1e5 + 5;
int a[NM], n;
long long ans;
map<int, queue<int>> mp;
vector<int> va[NM], dt[NM];
void fupd(int x, int y)
{
for (; x < NM; x += x & -x)
va[x].push_back(y);
}
void upd(int x, int y)
{
for (; x < NM; x += x & -x)
for (int i = upper_bound(all(va[x]), y) - va[x].begin(); i <= (int)va[x].size(); i += i & -i)
dt[x][i - 1]++;
}
int get(int x, int y)
{
int res = 0;
for (; x; x -= x & -x)
for (int i = upper_bound(all(va[x]), y) - va[x].begin(); i; i -= i & -i)
res += dt[x][i - 1];
return res;
}
long long count_swaps(std::vector<int> s) {
n = s.size();
for (int i = 1; i <= n; i++)
a[i] = s[i - 1];
vector<pair<int, int>> v;
for (int i = 1; i <= n; i++)
{
int t = a[i];
if (mp[-t].size())
{
if (t < 0)
ans++;
v.push_back({mp[-t].front(), i});
mp[-t].pop();
}
else
mp[t].push(i);
}
for (auto t : v)
fupd(t.fi, t.se);
for (int i = 1; i <= 1e5; i++)
{
sort(all(va[i])), va[i].erase(unique(all(va[i])), va[i].end());
dt[i].resize(va[i].size());
}
ans += 1ll * (n / 2) * (n / 2 - 1) / 2;
for (auto t : v)
upd(t.fi, t.se);
for (auto t : v)
{
ans += get(t.se, t.se) - get(t.fi - 1, t.se) - get(t.se, t.fi - 1) + get(t.fi - 1, t.fi - 1) - 1;
ans -= get(t.fi - 1, t.fi - 1);
}
return ans;
}
