#include "shoes.h"
#include <bits/stdc++.h>
#define uwu return
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
using namespace std;
const int SIZE = 2e5 + 5;
deque <int> r_pos[SIZE];
long long BITree[SIZE];
void add(int pos, int a){
for (pos = SIZE - pos; pos < SIZE; pos += (pos & -pos)){
BITree[pos] += a;
}
uwu;
}
long long query(int pos){
long long ret = 0;
for (pos = SIZE - pos; pos; pos -= (pos & -pos)){
ret += BITree[pos];
}
uwu ret;
}
long long count_cross(vector <pair<int, int>> intv){
vector <pair<int, int>> event;
for(auto i:intv){
event.push_back({i.fs, 1});
event.push_back({i.sc, -i.fs});
}
sort(all(event));
memset(BITree, 0, sizeof(BITree));
long long ret = 0;
for (auto i : event){
if(i.sc == 1){
add(i.fs, 1);
}
else{
add(-i.sc, -1);
ret += query(-i.sc);
}
}
uwu ret;
}
long long count_contains(vector <pair<int, int>> intv){
vector <pair<int, int>> event;
for(auto i:intv){
event.push_back({i.fs, 1});
event.push_back({i.sc, -i.fs});
}
sort(all(event));
memset(BITree, 0, sizeof(BITree));
long long ret = 0;
for (auto i : event){
if(i.sc != 1){
ret += query(-i.sc);
add(-i.sc, 1);
}
}
uwu ret;
}
long long count_swaps(vector<int> s) {
int N = s.size() / 2;
for (int i = 0; i < 2 * N; i++){
if(s[i] > 0)
r_pos[s[i]].push_back(i);
}
vector <pair<int, int>> team_up;
long long lr_swap = 0;
for (int i = 0; i < 2 * N; i++){
if(s[i] < 0){
team_up.push_back({i, r_pos[-s[i]].front()});
r_pos[-s[i]].pop_front();
if(team_up.back().sc < team_up.back().fs){
lr_swap++;
swap(team_up.back().fs, team_up.back().sc);
}
}
}
long long cs = count_cross(team_up), ct = count_contains(team_up);
// cerr << lr_swap << ' ' << cs << ' ' << ct << '\n';
uwu lr_swap + cs + 2 * ct;
}
