//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [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 = (int)s.size();
if (n == 0) return 0;
// pos indexed by value offset with adjust (keeps your approach).
int adjust = n + 50;
int SZ = (n * 2) + 100;
vector<vector<int>> pos(SZ);
for (int i = 0; i < n; ++i) {
int idx = adjust + s[i];
if (idx >= 0 && idx < SZ) pos[idx].push_back(i);
// else: value out of window -> ignored (or handle differently)
}
// pointers to next candidate in each pos vector (avoid re-scanning removed positions)
vector<int> ptr(SZ, 0);
BIT tr(n);
long long ans = 0;
for (int i = 0; i < n; ++i) {
if (tr.ask(i, i) == 0) continue; // i already removed
int key = adjust - s[i]; // we look for value == -s[i] originally
if (key < 0 || key >= SZ) continue; // no such bucket
auto &vec = pos[key];
int pidx = ptr[key];
// advance pointer to first vec[pidx] > i
while (pidx < (int)vec.size() && vec[pidx] <= i) ++pidx;
// advance pointer further if that position already removed
while (pidx < (int)vec.size() && tr.ask(vec[pidx], vec[pidx]) == 0) ++pidx;
// store back pointer
ptr[key] = pidx;
if (pidx >= (int)vec.size()) continue; // no valid partner
int p = vec[pidx];
if (p <= i) continue; // just in case, safety
// valid pair (i, p)
ans += tr.ask(i+1, p-1);
if (s[i] > 0) ans++;
tr.remove(p);
tr.remove(i);
// advance pointer since we removed vec[pidx]
++ptr[key];
}
return ans;
}
