#include "shoes.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
namespace{
struct BIT{
vector<int> bit;
int n;
BIT(int _n){
n = _n;
bit.resize(n + 1);
}
void modify(int pos, int val){
while(pos <= n){
bit[pos] += val;
pos += (pos & -pos);
}
}
int query(int pos){
int ans = 0;
while(pos > 0){
ans += bit[pos];
pos -= (pos & -pos);
}
return ans;
}
};
}
long long count_swaps(std::vector<int> s) {
ll ans = 0;
int n = (int)s.size() / 2;
vector<pair<int, int>> cp;
for(int i = 0; i < 2 * n; i++){
if(s[i] > 0) cp.emplace_back(s[i], i);
}
sort(cp.begin(), cp.end());
for(int i = 0; i < n; i++){
s[cp[i].second] = i + 1;
}
vector<pair<int, int>>().swap(cp);
for(int i = 0; i < 2 * n; i++){
if(s[i] < 0) cp.emplace_back(-s[i], i);
}
sort(cp.begin(), cp.end());
for(int i = 0; i < n; i++){
s[cp[i].second] = -(i + 1);
}
BIT bit(2 * n);
for(int i = 1; i <= 2 * n; i++) bit.modify(i, 1);
vector<pair<int, int>> pos(n + 1);
for(int i = 0; i < 2 * n; i++){
if(s[i] < 0) pos[-s[i]].first = i + 1;
else pos[s[i]].second = i + 1;
}
auto cmp = [&](pair<int, int> a, pair<int, int> b){
return a.first + a.second < b.first + b.second;
};
sort(next(pos.begin()), pos.end(), cmp);
for(int i = 1; i <= n; i++){
if(pos[i].first > pos[i].second) ans++;
ans += bit.query(pos[i].first) + bit.query(pos[i].second) - 3;
bit.modify(pos[i].first, -1);
bit.modify(pos[i].second, -1);
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run shoes.cpp grader.cpp
