#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} int readint(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,tsz,dfn[400005],dfo[400005],fenw[400005]; vector<int> ch[400005],ord; ll ans; void change(int p,int x){ for(;p<400005;p+=p&-p) fenw[p]+=x; } int query(int p){ int ret=0; for(;p;p-=p&-p) ret+=fenw[p]; return ret; } int make(){ int x=readint(); if(x){ dfn[x]=ord.size(); dfo[x]=ord.size(); ord.pb(x); return x; } int nd=++tsz; ch[nd].pb(make()); ch[nd].pb(make()); dfn[nd]=dfn[ch[nd][0]]; dfo[nd]=dfo[ch[nd][1]]; return nd; } void dfs(int x,bool ok){ if(x<=n){ if(ok) change(x,+1); return; } int szl=dfo[ch[x][0]]-dfn[ch[x][0]]; int szr=dfo[ch[x][1]]-dfn[ch[x][1]]; if(szl>szr) swap(szl,szr),swap(ch[x][0],ch[x][1]); dfs(ch[x][0],0); dfs(ch[x][1],1); ll inv=0; for(int i=dfn[ch[x][0]];i<=dfo[ch[x][0]];i++){ inv+=query(ord[i]-1); } inv=min(inv,(szl+1)*1ll*(szr+1)-inv); ans+=inv; if(ok) for(int i=dfn[ch[x][0]];i<=dfo[ch[x][0]];i++) change(ord[i],1); else for(int i=dfn[ch[x][1]];i<=dfo[ch[x][1]];i++) change(ord[i],-1); } int main(){ n=readint(); tsz=n; int rt=make(); dfs(rt,0); printf("%lld",ans); return 0; }