#include <bits/stdc++.h>
#include "shoes.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
queue<int> q2[100005];
struct FenwickTree {
vector<ll> bit; // binary indexed tree
int n;
FenwickTree(int n) {
this->n = n;
bit.assign(n, 0);
}
FenwickTree(vector<int> a) : FenwickTree(a.size()) {
for (size_t i = 0; i < a.size(); i++)
add(i, a[i]);
}
ll sum(int r) {
ll ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
ll sum(int l, int r) {
ll ret = sum(r);
if(l)ret -= sum(l - 1);
return ret;
}
void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
long long count_swaps(vector<int> s)
{
ll n = s.size();
vint copy = s;
int cnt = -1;
vector<bool> st(n+1);
for(int i = 0; i < n; i++)
{
if(s[i] < 0)
{
cnt+=2;
q2[-s[i]].push(cnt);
s[i] = cnt;
st[i] = true;
}
}
for(int i = 0; i < n; i++)
{
if(!st[i])
{
int prev = s[i];
s[i] = q2[s[i]].front()+1;
q2[prev].pop();
}
}
ll ans1 = 0;
FenwickTree ft(n+15);
for(int i = 0; i < n; i++)
{
ans1+=ft.sum(s[i]+1, n+10);
ft.add(s[i], 1);
}
s = copy;
cnt = n+2;
vector<bool> st2(n+1);
for(int i = n-1; i >= 0; i--)
{
if(s[i] > 0)
{
cnt-=2;
q2[s[i]].push(cnt);
s[i] = cnt;
st2[i] = true;
}
}
for(int i = n-1; i >= 0; i--)
{
if(!st2[i])
{
int prev = s[i];
s[i] = q2[-s[i]].front()-1;
q2[-prev].pop();
}
}
ll ans2 = 0;
FenwickTree ft2(n+15);
for(int i = 0; i < n; i++)
{
ans2+=ft2.sum(s[i]+1, n+10);
ft2.add(s[i], 1);
}
return min(ans1, ans2);
}
/*
int main()
{
int n;
cin >> n;
vint a(n);
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << count_swaps1(a) << endl;
cout << count_swaps2(a) << endl;
}
*/
/*
int main()
{
int bound = 2;
vint now;
for(int i = -bound; i <= bound; i++)
{
if(i != 0)
{
now.pb(i);
}
}
do {
if(count_swaps1(now) != count_swaps2(now))
{
cout << count_swaps1(now) << endl;
cout << count_swaps2(now) << endl;
for(auto x : now)
{
cout << x << " ";
}
cout << endl;
return 0;
}
} while (next_permutation(all(now)));
}
*/
/*
4
1 -2 -1 2
*/
