//Src : Vux2Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const ll N = 50000005;
ll sum[N], ls[N], rs[N];
ll root[N], l[N], r[N], val[N];
ll ans, s1, s2;
ll cnt, n, seg;
void init(ll ro) {
cin >> val[ro];
if (!val[ro]) {
l[ro] = ++cnt;
init(l[ro]);
r[ro] = ++cnt;
init(r[ro]);
}
}
void pushup(ll rt) {
sum[rt] = sum[ls[rt]] + sum[rs[rt]];
}
void build(ll l, ll r, ll &rt, ll key) {
if (!rt) rt = ++seg;
if (l == r) {
sum[rt]++;
return;
}
ll mid = (l + r) >> 1;
if (key <= mid) build(l, mid, ls[rt], key);
else build(mid + 1, r, rs[rt], key);
pushup(rt);
}
ll merge(ll r1, ll r2) {
if (!r1 || !r2) return r1 + r2;
s1 += (ll)sum[rs[r1]] * sum[ls[r2]];
s2 += (ll)sum[ls[r1]] * sum[rs[r2]];
ls[r1] = merge(ls[r1], ls[r2]);
rs[r1] = merge(rs[r1], rs[r2]);
pushup(r1);
return r1;
}
void solve(ll ro) {
if (!ro) return;
solve(l[ro]);
solve(r[ro]);
if (!val[ro]) {
s1 = s2 = 0;
root[ro] = merge(root[l[ro]], root[r[ro]]);
ans += min(s1, s2);
}
}
int main() {
ios::sync_with_stdio (0);
cin. tie (0);
cout. tie (0);
cin >> n;
cnt = 1;
init(1);
for (ll i = 1; i <= cnt; ++i)
if (val[i]) build(1, n, root[i], val[i]);
solve(1);
cout << ans;
return 0;
}
Compilation message
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
