//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define file(); freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define flush fflush(stdout);
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#define debug(...)
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
const double EPS = 1e-6;
const int MAXN = 1e5+10;
class BIT{
private:
vector<int> tr; int n;
public:
int lsb(int x){
return (x & -x);
}
BIT(int _n){
n = _n;
tr.resize(n+1, 1); //all are 1 s first
for(int i = 1; i <= n; i++){
if(i+lsb(i)<=n) tr[i+lsb(i)] += tr[i];
}
}
int till(int x){
int ans = 0;
while(x>0){
ans += tr[x];
x -= lsb(x);
}
return ans;
}
int ask(int l, int r){
l++, r++; // queries are 0 index based
if(l>r) return 0;
return till(r)-till(l-1);
}
void remove(int x){
x++;
while(x<=n){
tr[x] -= 1;
x += lsb(x);
}
return;
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size();
vii pos((n*2)+100);
int adjust = n+50;
ll ans = 0;
for(int i = 0; i < n; i++){
pos[adjust+s[i]].push_back(i);
}
BIT tr(n);
for(int i = 0; i < n; i++){
if(tr.ask(i, i)==0) continue;
int p = *upper_bound(all(pos[adjust-s[i]]), i);
ans += tr.ask(i+1, p-1);
if(s[i]>0) ans ++;
tr.remove(p);
tr.remove(i);
}
return ans;
}
