#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> seg;
map<int, vector<int>[2]> fr;
void afis(int st, int dr, int p)
{
cout<<st<<' '<<dr<<' '<<seg[p]<<'\n';
if(st == dr)
return;
int mij=(st+dr)/2;
afis(st, mij, 2*p);
afis(mij+1, dr, 2*p+1);
}
void upd(int i, int st, int dr, int p, int val)
{
if(st == dr)
{
seg[p]=val;
return;
}
int mij=(st+dr)/2;
if(i <= mij)
upd(i, st, mij, 2*p, val);
else
upd(i, mij+1, dr, 2*p+1, val);
seg[p]=seg[2*p] + seg[2*p+1];
}
long long query(int stt, int drt, int st, int dr, int p)
{
if(stt>drt)
return 0;
if(stt == st && drt == dr)
return seg[p];
int mij=(st+dr)/2;
if(drt<=mij)
return query(stt, drt, st, mij, 2*p);
if(stt>mij)
return query(stt, drt, mij+1, dr, 2*p+1);
return query(stt, mij, st, mij, 2*p) +
query(mij+1, drt, mij+1, dr, 2*p+1);
}
long long count_swaps(vector<int> v)
{
int n=v.size();
seg.resize(4*n + 4);
for(int i=(int)v.size()-1;i>=0;i--)
{
int tip = v[i] > 0 ? 1 : 0;
int x=abs(v[i]);
fr[x][tip].push_back(i);
upd(i, 0, n-1, 1, 1);
}
long long ans=0;
for(int i=0;i<(int)v.size();i++)
{
int tip = v[i] > 0 ? 1 : 0;
int x=abs(v[i]);
if(fr[x][tip].empty() || fr[x][tip].back() != i)
continue;
int per = fr[x][1-tip].back();
//cout<<i<<' '<<per<<'\n';
ans += query(i+1, per-1, 0, n-1, 1);
ans += tip;
fr[x][1-tip].pop_back();
fr[x][tip].pop_back();
upd(per, 0, n-1, 1, 0);
}
return ans;
}
