捞

有长度为 $n$ 的序列 $a_1,a_2,a_3,\cdots,a_n$

设 $d_i$ 为 $\max_{k=1}^{i-1}i\ [a_k>a_i]$

请问以下代码的期望复杂度及复杂度证明？

for(int i=1; i<=n; i++)
	for(int j=i; j>=0; j=d[j])
		//do something