#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 100000;
vector<long long> posDroites[NMAX+1];
vector<long long> posGauches[NMAX+1];
long long arbre[NMAX*3*2];
long long push[NMAX*3*2];
pair<long long, long long> debFin[NMAX*3*2];
long long iPosDroite[NMAX];
long long iPosGauche[NMAX];
//long long vals[NMAX];
bool vus[NMAX];
void init(long long noeud, long long deb, long long fin)
{
debFin[noeud] = {deb, fin};
if(deb == fin-1) return;
long long mil = (deb+fin)/2;
init(noeud*2, deb, mil);
init(noeud*2+1, mil, fin);
}
long long trouver(long long noeud, long long deb, long long fin)
{
arbre[noeud] += push[noeud];
if(debFin[noeud].first != debFin[noeud].second-1)
{
push[noeud*2] += push[noeud];
push[noeud*2+1] += push[noeud];
}
push[noeud] = 0;
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return 0;
if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin)) return arbre[noeud];
return trouver(noeud*2,deb, fin)+trouver(noeud*2+1, deb, fin);
}
long long chang(long long noeud, long long deb, long long fin)
{
arbre[noeud] += push[noeud];
if(debFin[noeud].first < debFin[noeud].second-1)
{
push[noeud*2] += push[noeud];
push[noeud*2+1] += push[noeud];
}
push[noeud] = 0;
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return arbre[noeud];
if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))
{
push[noeud]++;
return arbre[noeud]+1;
}
return arbre[noeud] = chang(noeud*2,deb, fin)+chang(noeud*2+1, deb, fin);
}
long long count_swaps(std::vector<int> s) {
long long nbVal = s.size()/2;
//long long nbG = 0;
for(long long a = 0; a < s.size(); a++)
{
long long i = s[a];
if(i > 0)
{
posDroites[i].push_back(a);
}
else
{
posGauches[-i].push_back(a);
}
}
//cout << "okmj" << endl;
long long somme = 0;
//long long decalage = 0;
init(1, 0, s.size());
int iEmePair = 0;
for(long long iPair = 0; iPair < s.size(); iPair++)
{
int val = s[iPair];
if(vus[iPair]) continue;
if(val < 0)
{
long long type = abs(val);
iPosGauche[type]++;
long long pos2 = posDroites[type][iPosDroite[type]]+trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1);
somme += (pos2-(iEmePair*2+1));
// cout << pos2 << endl;
// cout << trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1) << endl;
chang(1, 0, posDroites[type][iPosDroite[type]]);
vus[posDroites[type][iPosDroite[type]]] = true;
iPosDroite[type]++;
}
else
{
long long type = abs(val);
iPosDroite[type]++;
long long pos1 = posGauches[type][iPosGauche[type]]+trouver(1, posGauches[type][iPosGauche[type]], posGauches[type][iPosGauche[type]]+1);
somme += (pos1-iEmePair*2);
chang(1, 0, posGauches[type][iPosGauche[type]]);
vus[posGauches[type][iPosGauche[type]]] = true;
iPosGauche[type]++;
}
//cout << posGauche[iPair] << endl;
// cout << pos1 << " ";
//cout << posDroites[type].front()+trouver(1, posDroites[type].front(), posDroites[type].front()+1) << endl;
//somme += (pos2-pos1)-1;
//cout << "res : " << ((pos1-iPair*2)) << " " << (pos2-(iPair*2+1)) << " " << somme << endl;
iEmePair++;
}
return somme;
}
