#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll count_swaps(vector<int> S){
ll n = S.size()/2;
if(n == 1){
if(S[0] < 0){
return 0;
} else {
return 1;
}
}
vector<vector<ll>> vyskytR;
vector<vector<ll>> vyskytL;
for(ll i = 0;i <= n;i++){
vyskytL.push_back({});
vyskytR.push_back({});
}
ll sol = 0;
ll sqrtt = 1;
while(sqrtt * sqrtt < 2*n){
sqrtt++;
}
ll sqrtDec[n/sqrtt];
ll sum[2*n];
for(ll i = 0;i < 2*n/sqrtt;i++){
sqrtDec[i] = 0;
}
for(ll i = 0;i < 2*n;i++){
sum[i] = 0;
}
for(ll i = 0;i < 2*n;i++){
if(S[i] < 0){
vyskytL[-S[i]].push_back(i);
} else {
vyskytR[S[i]].push_back(i);
}
}
for(ll i = 0;i < n;i++){
reverse(vyskytR[i].begin(),vyskytR[i].end());
reverse(vyskytL[i].begin(),vyskytL[i].end());
}
ll where = 0;
ll where2 = 0;
ll countt = 0;
ll start;
ll shoes = n;
while(1){
if(where >= 2*n || shoes == 0){
break;
}
if(sum[where]==1){
where++;
continue;
}
if(S[where] < 0){
where2 = vyskytR[-S[where]][vyskytR[-S[where]].size()-1];
// countt sa nastavi na pocet pouzitych medzi where a where2
countt = 0;
start = where;
while(1){
if(start > where2){
break;
}
if(start % sqrtt == 0 && start+sqrtt-1 <= where2){
countt += sqrtDec[start/sqrtt];
start += sqrtt;
} else {
countt += sum[start];
start++;
}
//cout << countt << endl;
//cout << start << endl;
}
sol += where2-where-1-countt;
vyskytR[-S[where]].pop_back();
sum[where2] = 1;
sqrtDec[where2/sqrtt]++;
where++;
vyskytL[-S[where-1]].pop_back();
//cout << -S[where-1] << "???" << endl;
} else {
where2 = vyskytL[S[where]][vyskytL[S[where]].size()-1];
// countt sa nastavi na pocet pouzitych medzi where a where2
countt = 0;
start = where;
while(1){
if(start > where2){
break;
}
if(start % sqrtt == 0 && start+sqrtt-1 <= where2){
countt += sqrtDec[start/sqrtt];
start += sqrtt;
} else {
countt += sum[start];
start++;
}
}
sol += where2-where-countt;
vyskytL[S[where]].pop_back();
sum[where2] = 1;
sqrtDec[where2/sqrtt]++;
where++;
vyskytR[S[where-1]].pop_back();
}
shoes--;
//cout << countt << endl;
//cout << where-1 << " " << where2 << endl;
//cout << sol << endl;
//cout << "----" << endl;
}
//cout << sqrtt << endl;
return sol;
}
