#include <bits/stdc++.h> using namespace std; const int nx=4e5+5, fx=2e5+5; int n, cnt, t, x, sz[nx]; vector<int> d[nx]; struct fenwick { int d[fx]; void add(int i, int vl) { while (i<fx) d[i]+=vl, i+=(i&-i); } int query(int i) { int res=0; while (i>0) res+=d[i], i-=(i&-i); return res; } } f; void dfssz(int u) { sz[u]=1; for (auto v:d[u]) dfssz(v), sz[u]+=sz[v]; } pair<int, int> dfsvl(int u) { if (u<=n) return make_pair(f.query(u-1), f.query(fx-1)-f.query(u)); auto l=dfsvl(d[u][0]), r=dfsvl(d[u][1]); return make_pair(l.first+r.first, l.second+r.second); } void dfsrem(int u) { if (u<=n) return void(f.add(u, -1)); dfsrem(d[u][0]); dfsrem(d[u][1]); } void dfsadd(int u) { if (u<=n) return void(f.add(u, 1)); dfsadd(d[u][0]); dfsadd(d[u][1]); } int solve(int u, bool del) { if (u<=n&&!del) f.add(u, 1); if (u<=n) return 0; if (sz[d[u][0]]<sz[d[u][1]]) swap(d[u][0], d[u][1]); int res=solve(d[u][1], 1)+solve(d[u][0], 0); auto tmp=dfsvl(d[u][1]); if (del) dfsrem(u); else dfsadd(d[u][1]); //cout<<u<<' '<<res<<' '<<tmp.first<<' '<<tmp.second<<' '<<min(tmp.first, tmp.second)<<'\n'; return res+min(tmp.first, tmp.second); } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>x; t=n+1; while (cnt!=n) { cin>>x; if (!x) d[t].push_back(t+1), t++; else d[t].push_back(x), t-=(d[t].size()==2), cnt++; } dfssz(n+1); cout<<solve(n+1, 0); } /* 5 0 0 0 5 1 2 0 4 3 */