#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
vector<int> operator + (vector<int>& a, vector<int>& b){
vector<int> res;
int i = 0, j = 0, n = a.size(), m = b.size();
while(i < n && j < m){
while(i < n && a[i] <= b[j])
res.push_back(a[i++]);
if (i == n) break;
while(j < m && b[j] <= a[i])
res.push_back(b[j++]);
}
while(i < n)
res.push_back(a[i++]);
while(j < m)
res.push_back(b[j++]);
return res;
}
struct SEGMENT_TREE{
vector<vector<int>> st;
inline SEGMENT_TREE(int n, vector<int>& vec){
st.resize(4 * n);
build(1, 0, n - 1, vec);
}
inline void build(int ind, int l, int r, vector<int>& vec){
if (l == r){
st[ind].push_back(vec[l]);
return;
}
int mid = (l + r) >> 1;
build(ind << 1, l, mid, vec);
build(ind << 1 | 1, mid + 1, r, vec);
st[ind] = st[ind << 1] + st[ind << 1 | 1];
return;
}
inline long long get(int ind, int l, int r, int lb, int rb, int val){
if (lb > rb) return 0;
if (lb <= l && r <= rb){
int it = upper_bound(st[ind].begin(), st[ind].end(), val) - st[ind].begin();
return st[ind].size() - it;
}
int mid = (l + r) >> 1;
long long ans = 0;
if (mid >= lb) ans += get(ind << 1, l, mid, lb, rb, val);
if (mid < rb) ans += get(ind << 1 | 1, mid + 1, r, lb, rb, val);
return ans;
}
};
inline long long count_swaps(vector<int> a){
int n = a.size() / 2;
long long res = 0;
queue<int> q[2 * n + 1];
vector<int> last_ind (a.size());
for (int i = 0; i < a.size(); ++i){
if (q[-a[i] + n].empty()){
q[a[i] + n].push(i);
last_ind[i] = i;
}
else{
int pre = q[-a[i] + n].front();
q[-a[i] + n].pop();
last_ind[i] = pre;
}
}
SEGMENT_TREE seg((int)a.size(), last_ind);
for (int i = 0; i < a.size(); ++i) if (last_ind[i] != i){
res += seg.get(1, 0, a.size() - 1, last_ind[i] + 1, i - 1, last_ind[i]);
if (a[last_ind[i]] > 0) res++;
}
return res;
}
