rt，赛时做法是先求出每个隔板左边离他最近且比他高的隔板编号，然后瞎搞即可。

即用 $pre$ 数组表示当前隔板左边最后一个比他高的隔板编号，该部分代码：

for(int i=1;i<=n;i++)
	{
		pre[i]=i-1;
		while(a[pre[i]]<a[i]&&pre[i]!=0)pre[i]=pre[pre[i]];
	}

这么写赛时通过了，但是如何证明复杂度？