#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SZ(x) int((x).size())
#define all(x) (x).begin() , (x).end()
#define sep ' '
const int MAXN = 2e5 + 10;
int n , fen[MAXN] , mark[MAXN];
vector<int> pos[MAXN];
void add(int x , int v){
for(x++; x < MAXN ; x += x & -x) fen[x] += v;
}
int get(int x){
int ans = 0;
for(x++ ; x > 0 ; x -= x & -x) ans += fen[x];
return ans;
}
ll count_swaps(vector<int> s) {
n = SZ(s) / 2; ll ans = 0;
for(int i = 0 ; i < n * 2 ; i++){
s[i] += n; add(i , 1);
pos[s[i]].push_back(i);
}
for(int i = 0 ; i < MAXN ; i++) reverse(all(pos[i]));
for(int i = 0 ; i < n * 2 ; i++){
if(mark[i]) continue;
int x = i , y = pos[n + n - s[i]].back();
pos[s[i]].pop_back(); pos[n + n - s[i]].pop_back();
mark[x] = mark[y] = 1;
// cout << x << sep << y << sep << get(x) << sep << get(y) << endl;
ans += get(y) - get(x) - (s[x] < s[y]);
add(x , 1); add(y , -1);
}
return ans;
}
