#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define pb push_back
#define eb emplace_back
ll count_swaps1(std::vector<int> s) {
int n2 = s.size();
int n = n2/2;
vector<pii> m;
m.reserve(n);
vector<vi> p(n+1);
for(int i=0; i<n2; i++){
if(s[i] < 0){
m.eb(-s[i], i);
}
else{
p[s[i]].pb(i);
}
}
for(int i=1; i<=n; i++){
reverse(p[i].begin(), p[i].end());
}
vector<int> c;
c.reserve(n2);
for(int i=0; i<n; i++){
auto& [si, mi] = m[i];
c.pb(mi);
c.pb(p[si].back());
p[si].pop_back();
}
ll ans = 0;
for(int t=0; t<n2; t++){
for(int i=1; i<n2; i++){
if(c[i-1] > c[i]){
swap(c[i-1], c[i]);
ans++;
}
}
}
return ans;
}
ll count_swaps(std::vector<int> s) {
ll ans = 0;
ans = max(ans, count_swaps1(s));
reverse(s.begin(), s.end());
for(auto& i: s){
i = -i;
}
ans = max(ans, count_swaps1(s));
return ans;
}
