#include "shoes.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
constexpr ll inf = (1ll<<60);
struct binary_indexed_tree{
vi node;
ll N;
binary_indexed_tree(int n): N(n){
node.resize(N+1);
}
void add(ll idx, ll val){
idx++;
for(; idx<=N; idx+=(idx&-idx)) node[idx] += val;
}
ll sum(ll idx){
idx++;
ll ret = 0;
for(; 0<idx; idx-=(idx&-idx)) ret += node[idx];
return ret;
}
};
long long subtask_2_5(std::vector<int> s) {
ll N = s.size();
vii idx(N+1);
rep(i,0,N){
if(s[i] > 0) idx[s[i]].pb(i);
}
REP(i,0,N) reverse(all(idx[i]));
vector<bool> used(N);
binary_indexed_tree bit(N+1);
rep(i,0,N) bit.add(i,1);
ll ans = 0;
rep(i,0,N/2){
ll min = inf;
rep(j,0,N){
if(used[j]) continue;
if(s[j] > 0) continue;
ll val = -s[j];
ll cost = bit.sum(j)-1;
ll p = idx[val].back();
cost += bit.sum(p)-1;
if(j < p) cost--;
min = std::min(min, cost);
}
ans += min;
rep(j,0,N){
if(used[j]) continue;
if(s[j] > 0) continue;
ll val = -s[j];
ll cost = bit.sum(j)-1;
ll p = idx[val].back();
cost += bit.sum(p)-1;
if(j < p) cost--;
if(min == cost){
used[j] = used[p] = true;
bit.add(j,-1);
bit.add(p,-1);
idx[val].pop_back();
break;
}
}
}
return ans;
}
long long count_swaps(std::vector<int> s) {
ll N = s.size();
//if(N/2 <= 1000) return subtask_2_5(s);
vii idx(N+1);
rep(i,0,N){
if(s[i] > 0) idx[s[i]].pb(i);
}
REP(i,0,N) reverse(all(idx[i]));
vi p(N);
ll now = 0;
vector<std::tuple<ll,ll,ll>> data;
rep(i,0,N){
if(s[i] > 0) continue;
ll val = -s[i];
ll cost = i+idx[val].back();
if(i < idx[val].back()) cost--;
data.pb(mtp(cost, i, idx[val].back()));
idx[val].pop_back();
}
sort(all(data));
for(auto el: data){
ll x,y,z; std::tie(x,y,z) = el;
p[now++] = y;
p[now++] = z;
}
ll ans = 0;
binary_indexed_tree bit(N);
rep(i,0,N){
ans += i-bit.sum(p[i]);
bit.add(p[i],1);
}
return ans;
}
