#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
const int N = 1e5+5;
const int M = 1e3+5;
set<int> S[N];
int bel[N], en[N], st[N];
ll count_swaps(vector<int> v){
int n = (int)v.size(), ok = 1;
n /= 2;
for(int i = 0; i < n; ++i)
ok &= (v[i] < 0);
for(int i = 0; i < n; ++i)
ok &= (-v[i] == v[i+n]);
ll ans = 0;
if(ok){ // subtask 4
n--;
ans = n*1ll*(n+1)/2;
return ans;
}
n *= 2, ok = 1;
for(int i = 1; i < n; ++i)
ok &= (abs(v[0]) == abs(v[i]));
if(ok){ // subtaksk 3
int ne_ = 1, ne__ = 1;
for(int i = 0; i < n; ++i){
ne_ = max(i+1, ne_);
ne__ = max(i+1, ne__);
if(!(i&1)){
if (v[i] < 0)
continue;
while(v[ne_] > 0)
ne_++;
swap(v[i], v[ne_]);
ans += (ne_-i);
}
if(i&1){
if(v[i] > 0)
continue;
while (v[ne__] < 0)
ne__++;
swap(v[i], v[ne__]);
ans += (ne__-i);
}
}
return ans;
}
// subtask 1, 2, 5, 6
vector<int> vis(n, 0);
// I need to write sqrt decomposition
for(int i = 0; i < n; ++i)
S[v[i]+n].insert(i);
int ad = sqrt(n);
vector<int> cnt(M);
int nire = -1;
for(int i = 0; i < n; ++i){
int pk = i/ad;
bel[i] = pk, cnt[pk]++, en[pk] = i;
if(pk > nire)
st[pk] = i;
nire = pk;
}
for(int i = 0; i < n-1; i++){
if(vis[i])
continue;
if(v[i] > 0)
ans++;
auto j_ = S[-v[i]+n].upper_bound(i);
S[-v[i]+n].erase(j_);
int j = *j_;
vis[j] = 1, cnt[bel[j]]--;
int l = i+1, r = j-1;
if(bel[l] == bel[r]){
for(int k = l; k <= r; ++k)
ans += (!vis[k]);
continue;
}
for(int k = l; k <= en[l]; ++k)
ans += (!vis[bel[k]]);
for(int k = st[r]; k <= r; ++k)
ans += (!vis[bel[k]]);
for(int k = l+1; k < r; ++k)
ans += (cnt[bel[k]]);
}
return ans;
}
