---

这个题目做法是o(n)的，但是网上流传了大量o(nlogn)甚至o(n^2)的伪算法

首先，二叉搜索树的所有节点是从左到右的，按顺序插入的节点一定不可能排在父节点前面。

于是我们将节点放在二维平面内，a[i]坐标为(a[i],i)，i越小，高度越高

可以证明两个结论：

1.二叉查找树两个节点i,j若互相不为对方的祖先，则有最近公共祖先x，a[i]与a[j]一个比a[x]大，一个比a[x]小。

反证：如果两个都比a[x]大或者比a[x]小，则两个节点在x的同一个子树中，x不是最近公共祖先。

2.数值上处于任何一个节点的父节点及其本身之间的所有节点都是其子树中的节点。（由二叉查找树定义）

然后我们以双向链表的形式存储1-n这些数，从高度最低的节点开始，每个节点的父节点一定是其相邻节点中高度最低的（如果不是，那么相邻的两个节点的最近公共祖先是其中一个节点的子节点，不符合条件），遍历一个节点之后从链表中删除它。

#include <iostream>
using namespace std;
const int MAXN=100001;
int a[MAXN],last[MAXN],n,height[MAXN],L[MAXN],R[MAXN];
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		height[a[i]]=i;
		if (i>=1) L[i]=i-1;
		if (i<n) R[i]=i+1;
	}

	for (int i=n;i>1;i--){
		if (height[L[a[i]]]>height[R[a[i]]]) {
				last[a[i]]=L[a[i]];
				R[L[a[i]]]=R[a[i]];
		}
			else {
				last[a[i]]=R[a[i]];
				L[R[a[i]]]=L[a[i]];
			}
		}
	for (int i=1;i<=n;i++)
		cout<<last[i]<<' ';
}