题目链接https://codeforces.com/contest/1220/problem/F

---

题意

给出一个排列，每一次操作可以把最前面的数字放到最后面。问至少要几次操作，可以使得对此时的排列建笛卡尔树深度最小。

---

题解

每次把最左边的数放到最右边，那么对于根节点的左右两棵子树，左边子树的深度一定是单调非增的，右边子树的深度一定是单调非减的。所以我们可以先二分出一个位置得出最小深度，然后再二分得出最小深度的最左侧位置。
当然根节点也可能会被置换到右边，那就把根节点置换到最右边然后再计算一次答案就行了。
好像有更简单的做法，待补。

---

#include<bits/stdc++.h>
using namespace  std;
typedef long long ll;
const int N=2e5+5;
int n,ls[N],rs[N],vis[N],stk[N],rt;
int dg[N];
int a[N],b[N],c[N];
void build(){
    int top=0;
    for(int i=1;i<=n;i++){
        ls[i]=0,rs[i]=0,vis[i]=0;
    }
    for(int i=1;i<=n;i++){
        int k=top;
        while(k>0&&a[stk[k-1]]>a[i]) k--;
        if(k) rs[stk[k-1]]=i;
        if(k<top) ls[i]=stk[k];
        stk[k++]=i;
        top=k;
    }
    for(int i=1;i<=n;i++){
        vis[ls[i]]=vis[rs[i]]=1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0) rt=i;
    }
}
void dfs(int u){
    dg[u]=1;
    if(ls[u]) dfs(ls[u]),dg[u]=max(dg[u],dg[ls[u]]+1);
    if(rs[u]) dfs(rs[u]),dg[u]=max(dg[u],dg[rs[u]]+1);
}
pair<int,int>solve(int p){

    build();dfs(rt);
    if(dg[ls[rt]]<=dg[rs[rt]]) return pair<int,int>(dg[rt],0);

    int lo=0,hi=p-1,res,ans;
    while(lo<=hi){
        int mid=lo+hi>>1;
        for(int i=mid%n+1,j=1;j<=n;j++,i=i%n+1){
            b[j]=a[i];
            c[j]=a[j];
        }
        for(int i=1;i<=n;i++) a[i]=b[i];
        build();dfs(rt);
        if(dg[ls[rt]]>=dg[rs[rt]]) res=mid,lo=mid+1,ans=dg[rt];
        else hi=mid-1;
        for(int i=1;i<=n;i++) a[i]=c[i];
    }

    lo=0,hi=res;
    while(lo<=hi){
        int mid=lo+hi>>1;
        for(int i=mid%n+1,j=1;j<=n;j++,i=i%n+1){
            b[j]=a[i];
            c[j]=a[j];
        }
        for(int i=1;i<=n;i++) a[i]=b[i];
        build();dfs(rt);
        if(dg[rt]==ans) res=mid,hi=mid-1;
        else lo=mid+1;
        for(int i=1;i<=n;i++) a[i]=c[i];
    }
    return pair<int,int>(ans,res);
}
int main(){
    scanf("%d",&n);
    int p=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==1) p=i;
    }
    pair<int,int> ans1=solve(p);
    for(int i=p%n+1,j=1;j<=n;j++,i=i%n+1){
        b[j]=a[i];
    }
    for(int i=1;i<=n;i++) a[i]=b[i];
    pair<int,int> ans2=solve(n);
    ans2.second+=p;
    if(ans1.first>ans2.first) swap(ans1,ans2);
    if(ans1.first==ans2.first){
        if(ans1.second>ans2.second) swap(ans1,ans2);
    }
    printf("%d %d\n",ans1.first,ans1.second);
    return 0;
}