首先笛卡尔树可以用 $O(N)$ 做。

但我太懒所以直接核弹打蚊子纯模拟 $O(N \log N)$ 做法：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct node{int l,r,id;}tr[N<<2];
int a[N];
void pushup(int p)
{
	int mn=1e9;
	if(a[tr[lc(p)].id]<mn)
		mn=a[tr[lc(p)].id],tr[p].id=tr[lc(p)].id;
	if(a[tr[rc(p)].id]<mn)
		mn=a[tr[rc(p)].id],tr[p].id=tr[rc(p)].id;
}
void bt(int p,int l,int r)
{
	tr[p]={l,r,0};
	if(l==r){tr[p].id=l;return;}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);bt(rc(p),mid+1,r);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(tr[p].r<l||tr[p].l>r)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].id;
	int mn=1e9;
	int id1=query(lc(p),l,r),id2=query(rc(p),l,r);
	if(a[id1]<a[id2])return id1;
	return id2;
}
int fa[N];
void build(int f,int l,int r)
{
	if(l>r)return;
	int id=query(1,l,r);
	fa[id]=f;
	build(id,l,id-1);build(id,id+1,r);
}
int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];a[0]=2e9;
	bt(1,1,n);
	build(0,1,n);
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==0)cout<<i-1<<' ';
		else cout<<fa[i]-1<<' ';
	}
	return 0;
}