#include "shoes.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const ll N=2e5+5;
ll t[4*N],lazy[4*N];
ll MAXVAL=4e5+5;
void update(int idx,int val){
while(idx<MAXVAL){
t[idx]+=val;
idx+=(idx&(-idx));
}
}
ll get(int idx){
int sum=0;
while(idx>0){
sum+=t[idx];
idx-=(idx&(-idx));
}
return sum;
}
long long count_swaps(vector<int> s) {
reverse(s.begin(),s.end());
s.pb(1);
reverse(s.begin(),s.end());
int n=s.size()-1;
vector <ll > a[n+1],b[n+1];
ll ind1[n+5],ind2[n+5];
bool fix[n+5];
for (int i=1; i<=n; i++) fix[i]=0;
ll x,y,z=0,ans=0;
for (int i=1; i<=n; i++)
{
ind1[i]=ind2[i]=0;
if (s[i]>0) { a[s[i]].pb(i); }
else b[abs(s[i])].pb(i);
}
vector <pair<ll,ll> > v;
v.clear();
v.pb(mp(0,0));
for (int i=1; i<=n; i++){
if (fix[i]==1) continue;
if (s[i]<0){
v.pb(mp(i,a[abs(s[i])][ind1[abs(s[i])]])); fix[a[abs(s[i])][ind1[abs(s[i])]]]=1; ind1[abs(s[i])]++; ind2[abs(s[i])]++;
}
else
{
v.pb(mp(i,b[abs(s[i])][ind2[abs(s[i])]])); fix[b[abs(s[i])][ind2[abs(s[i])]]]=1; ind2[abs(s[i])]++; ind1[abs(s[i])]++;
}
}
ans=0; ll add=0;
for (int i=1; i<=n/2; i++){
z++;
x=v[i].f; y=v[i].s;
add=get(x-1); x+=add;
ans+=x-z;
update(x,1);
z++;
add=get(y-1); y+=add;
ans+=y-z;
if (s[x]>0) ans++;
}
return ans;
}
/*
int main() {
int n;
assert(1 == scanf("%d", &n));
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
assert(1 == scanf("%d", &S[i]));
fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
fclose(stdout);
return 0;
}*/
