#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define par pair<int,int>
#define f first
#define s second
#define ld long duble
#define ull unsigned long long
#define st short int
using namespace std;
int abi[1000006],N;
void add(int k){
while(k<=N) abi[k]++,k+=k&-k;
}
ll query(int k){
ll s=0;
while(k) s+=abi[k],k-=k&-k;
return s;
}
long long count_swaps(std::vector<int> vec) {
stack <int> pila1,pila2,pilam1,pilam2;
for(int i=vec.size()-1;i>=0;i--){
if(vec[i]==1) pila1.push(i);
if(vec[i]==-1) pilam1.push(i);
if(vec[i]==2) pila2.push(i);
if(vec[i]==-2) pilam2.push(i);
}
int n=vec.size();
N=n;
ll solve=0;
fill(abi,abi+n,0);
bool vis[n];
fill(vis,vis+n,false);
for(int i=0;i<n;i++){
if(vis[i]) continue;
if(vec[i]==1){
if(pilam1.empty()) continue;
while(pilam1.top()<i){
pilam1.pop();
if(pilam1.empty()) break;
}
if(pilam1.empty()) continue;
solve+=pilam1.top()-i-query(pilam1.top())+query(i);
add(pilam1.top());
vis[pilam1.top()]=true;
pilam1.pop();
}
if(vec[i]==-1){
if(pila1.empty()) continue;
while(pila1.top()<i){
pila1.pop();
if(pila1.empty()) break;
}
if(pila1.empty()) continue;
solve+=pila1.top()-i-1-query(pila1.top())+query(i);
add(pila1.top());
vis[pila1.top()]=true;
pila1.pop();
}
if(vec[i]==2){
if(pilam2.empty()) continue;
while(pilam2.top()<i){
pilam2.pop();
if(pilam2.empty()) break;
}
if(pilam2.empty()) continue;
solve+=pilam2.top()-i-query(pilam2.top())+query(i);
add(pilam2.top());
vis[pilam2.top()]=true;
pilam2.pop();
}
if(vec[i]==-2){
if(pila2.empty()) continue;
while(pila2.top()<i){
pila2.pop();
if(pila2.empty()) break;
}
if(pila2.empty()) continue;
solve+=pila2.top()-i-1-query(pila2.top())+query(i);
add(pila2.top());
vis[pila2.top()]=true;
pila2.pop();
}
}
return solve;
}
