题意：给你一个1~N的排列，然后让你按顺序把它们插到一个二叉搜索树里，然后问能插出同样的二叉搜索树的 字典序最小的排列是什么

本来可以直接模拟建树然后dfs一下输出结果...然而有可能会退化成链，最差复杂度是O($n^2$)

然后貌似这题可以用笛卡尔树，先对输入排序然后实现O(n)建树..但我不会

考虑线段树做法，按照权值建线段树，维护区间中最小的序号

那我从根节点开始做（输入和输出的第一个数一定相同），每次找它左子树对应的权值区间范围中最小的序号，就是左子树的根；右子树同理

这样一直做下来，每做到一个数直接输出即可

复杂度是O(nlogn)

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int maxn=100100; 8  9 int mi[maxn*4],val[maxn],N;10 11 void insert(int p,int l,int r,int x,int y){12     if(l==r) mi[p]=y;13     else{14         int m=l+r>>1;15         if(x<=m) insert(p<<1,l,m,x,y);16         else insert(p<<1|1,m+1,r,x,y);17         mi[p]=min(mi[p<<1],mi[p<<1|1]);18     }19 }20 int query(int p,int l,int r,int x,int y){21     if(x<=l&&r<=y) return mi[p];22     else{23         int m=l+r>>1;int re=0x3f3f3f3f;24         if(x<=m) re=min(query(p<<1,l,m,x,y),re);25         if(y>m) re=min(query(p<<1|1,m+1,r,x,y),re);26         return re;27     }28 }29 30 void solve(int x,int l,int r){31     if(x) printf("%d ",x);32     if(x>l+1) solve(val[query(1,1,N,l+1,x-1)],l,x);33     if(x