inline int lca(int x,int y){    if(x>y)    swap(x,y);

     return (h[rmq[log[y-x+]][x]]<h[rmq[log[y-x+]][y-near[y-x+]+]])?

     rmq[log[y-x+]][x]:rmq[log[y-x+]][y-near[y-x+]+];}

     build(,);

     for(int i=;i<=N;i++)

         rmq[][i]=list[i];

     for(int i=,j=,k=;i<=N;log[i]=j,near[i]=k,i++)

         if(i>k*)    j++,k*=;

     for(int i=,k=;k<=N;i++,k*=)

         for(int j=;j<=N-k+;j++)

             rmq[i][j]=(h[rmq[i-][j]]<h[rmq[i-][j+k/]])?rmq[i-][j]:rmq[i-][j+k/];