#include "shoes.h"
#include <bits/stdc++.h>
#define lll long long
#define emb emplace_back
#define em emplace
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pii pair <int, int>
using namespace std;
const int N = 2e5 + 5;
struct {
int lazy[4 * N], seg[4 * N];
void push(int l, int r, int i){
seg[i] += lazy[i] * (r - l + 1);
if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
lazy[i] = 0;
}
void update(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) {
lazy[i] += val;
push(l, r, i);
return;
}
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
update(l, mid, 2 * i, ll, rr, val);
update(mid + 1, r, 2 * i + 1, ll, rr, val);
seg[i] = seg[2 * i] + seg[2 * i + 1];
}
int query(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return seg[i];
if (r < ll || l > rr) return 0;
int mid = (l + r) / 2;
return query(l, mid, 2 * i, ll, rr) + query(mid + 1, r, 2 * i + 1, ll, rr);
}
} seg;
lll count_swaps(vector<int> a) {
int n = a.size()/2;
reverse(all(a)); a.emb(0); reverse(all(a));
lll ans = 0;
map <int, set <int>> mp;
for (int i = 1; i <= 2*n; i++) mp[a[i]].em(i);
for (int i = 1; i <= 2*n; i++) {
if (i % 2 == 0) continue;
int idx = i - seg.query(1, 2*n, 1, i, i);
int cur = *mp[a[idx] * -1].begin();
cout << i << ": " << cur << "\n";
mp[a[idx] * -1].erase(cur);
mp[a[idx]].erase(idx);
cur += seg.query(1, 2*n, 1, cur, cur);
int cnt = 0;
if (a[idx] < 0) cnt = cur - i - 1;
else cnt += cur - i;
ans += cnt;
// cout << i << ": " << "[" << idx << ", " << cur << "] : " << cnt << "\n";
seg.update(1, 2*n, 1, idx, cur, 1);
// for (auto e : a) cout << e << " "; cout << " : " << cnt << "\n";
}
return ans;
}
/*
sub3: find closest position
sub4:
-1 1 : 0
-1 -2 1 2 : 1
-1 -2 -3 1 2 3 : 3
ans = n(n-1)/2
sub5: n^2
for each idx i: find closest left/right shoe then
just count number of swaps, then change index of
other shoes accordingly..?
_,_,_,X,_,_,Y,_,X,_,_,Y
-3 2 1 -2 3 1
3 2 1 -2 -3 -1
-3 3 2 1 -2 -1: 4 : [3, 5] idx -1
-3 3 -2 2 1 -1: 2 : [5, 5] idx -1
-3 3 -2 2 -1 1: 1 : no change
[-2, 1, -2, 2, -1, 2]
[-2, 2, 1, -2, -1, 2] : 2
[-2, 2, -1, 1, -2, 2] : 2
*/
