struct CartesianTree
{
static const int __=50005;
struct node
{
int val,key,id,fa,lson,rson;
void clear(){fa=lson=rson=0;}
bool operator<(const node &b)const
{
return val<b.val;
}
}t[__];
CartesianTree() {clear();}
node& operator[](int x){return t[x];}
int root;
stack<int>S;
void build(int n)
{
sort(t+1,t+n+1);
for(int i=1;i<=n;++i)
{
while(!S.empty() && t[S.top()].key>t[i].key)
S.pop();
t[i].clear();
if(S.empty())
{
t[root].fa=i;
t[i].lson=root;
root=i,S.push(i);
continue;
}
t[i].lson=t[S.top()].rson;
t[t[S.top()].rson].fa=i;
t[S.top()].rson=i;
t[i].fa=S.top();
S.push(i);
}
}
void clear(){for(root=0;!S.empty();S.pop());}
}ct;
