#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
bool Ordenado(vector<int> s){
bool S_ = 1;
for(long long i = 0; i < (long long)s.size(); i += 2){ if(!(s[i] < 0 and s[i + 1] == -s[i])) S_ = 0; cout<<s[i]<<" "<<s[i + 1]<<" "; }
cout<<"\n";
return S_;
}
vector<long long> _rbol;
vector<long long> Jaja;
vector<long long> m;
void Crear(long long Izquierda, long long Derecha, long long Posici_n){
if(Izquierda == Derecha){
_rbol[Posici_n] = m[Izquierda];
Jaja[Izquierda] = Posici_n;
} else {
long long Promedio = (Izquierda + Derecha) / 2;
Crear(Izquierda, Promedio, Posici_n * 2);
Crear(Promedio + 1, Derecha, Posici_n * 2 + 1);
_rbol[Posici_n] = _rbol[Posici_n * 2] + _rbol[Posici_n * 2 + 1];
}
}
long long Consulta(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
if(Izquierda >= Inicio and Derecha <= Final) return _rbol[Posici_n];
else if(Izquierda > Final or Derecha < Inicio) return 0;
else {
long long Promedio = (Izquierda + Derecha) / 2;
return Consulta(Izquierda, Promedio, Posici_n * 2, Inicio, Final) + Consulta(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final);
}
}
void Actualizar(long long Posici_n, long long Valor, long long Original){
if(Posici_n == 0) return;
if(Posici_n == Original) _rbol[Posici_n] = Valor;
else _rbol[Posici_n] = _rbol[Posici_n * 2] + _rbol[Posici_n * 2 + 1];
Actualizar(Posici_n / 2, Valor, Original);
}
long long count_swaps(vector<int> s){
long long n = s.size();
/*if(n == 2){
if(s[0] < 0) return 0;
else return 1;
} else if(n <= 2222222){*/
/*long long Contador = 0;
for(long long i = 0; i < n; i++){
if(i % 2 == 0){
if(s[i] > 0){
for(long long j = i; j < n; j++){
if(s[j] == -s[i]){
for(long long k = j; k > i; k--){
swap(s[k], s[k - 1]);
Contador++;
}
break;
}
}
}
} else {
if(!(s[i] == -s[i - 1] and s[i] > 0)){
for(long long j = i; j < n; j++){
if(s[j] == -s[i - 1]){
for(long long k = j; k > i; k--){
swap(s[k], s[k - 1]);
Contador++;
}
break;
}
}
}
}
}
return Contador;*/
bool Subtarea_4 = 1;
for(long long i = 0; i < n / 2; i++) if(s[i] > 0 or s[i] != -s[i + n / 2]) Subtarea_4 = 0;
if(Subtarea_4){
n /= 2;
return n * (n - 1) / 2;
}
m.assign(n, 1);
Jaja.assign(n, 0);
_rbol.assign(n * 4, 0);
n--;
Crear(0, n, 1);
long long Contador = 0;
for(long long i = 0; i <= n; i++){
if(m[i] == 1){
/*if(i % 2 == 0){
if(s[i] > 0){*/
for(long long j = i + 1; j <= n; j++){
if(m[j] == 1){
if(s[j] == -s[i]){
m[j] = 0;
Actualizar(Jaja[j], 0, Jaja[j]);
Contador += Consulta(0, n, 1, i, j - 1);
if(s[i] < 0) Contador--;
//cout<<i<<" "<<j<<" "<<Contador<<"\n";
break;
}
}
}
/*}
} else {
if(!(s[i] == -s[i - 1] and s[i] > 0)){
for(long long j = i; j <= n; j++){
if(m[i] == 1){
if(s[j] == -s[i - 1]){
m[i] = 0;
Actualizar(Jaja[i], 0, Jaja[i]);
Contador += Consulta(0, n, 1, i, j - 1);
break;
}
}
}
}
}*/
}
m[i] = 0;
Actualizar(Jaja[i], 0, Jaja[i]);
}
return Contador;
/*} else {
n /= 2;
return n * (n - 1) / 2;
}*/
}
