Of course, the solution of monotone stack is not mentioned here.

Talk about the solution of Cartesian tree

In fact, as soon as this question comes out, anyone who has studied Descartes tree should know how to solve it.

If the first K terms of two sequences satisfy the requirement that their subsets have the same minimum position, then the Cartesian tree constructed by the first K terms of their array is actually the same.

Method 1. Divide each length len into two parts, then construct the first len term of the sequence, and then determine whether the number is the same. The rule of judgment is whether the father node and the son node of each node are the same.

Method 2. Actually, people who are familiar with the nature of Descartes tree know that Descartes tree is constructed to position i so that all nodes 1 to i-1 are on the left.

Drawing a picture shows that the maximum length required is actually whether the prefixes of the two Cartesian trees are the same, that is to say, after removing the nodes behind len, the shape of the tree is exactly the same.

So how can we make more elegant judgments???

In fact, we only need to consider whether the left son in the first place is the same or not. If the left son in the first place is the same, the shape of the first item must be the same. For a node, its left son node must be smaller than others, and its right son node must be larger than him. i don't know how to prove it.

Method 1:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int stk[maxn],tp;
int aa[maxn],bb[maxn];
void build(int n,int a[],int ch[][2],int fa[]){
   tp=0;
   for (int i=1;i<=n;i++)
   {
       int last=0;
       while(tp){
          if (a[stk[tp]]<=a[i]){
             if (ch[stk[tp]][1])ch[i][0]=ch[stk[tp]][1],fa[ch[stk[tp]][1]]=i;
             ch[stk[tp]][1]=i;fa[i]=stk[tp];
             break;
          }
          last=stk[tp--];
       }
       if (!tp && last)ch[i][0]=last,fa[last]=i;
       stk[++tp]=i;
   }
}
int fa[maxn],ch[maxn][2],faa[maxn],chh[maxn][2];
bool same(int len){
    for (int i=1;i<=len;i++){
        fa[i]=0;
        ch[i][0]=0;
        ch[i][1]=0;
        faa[i]=0;
        chh[i][0]=0;
        chh[i][1]=0;
    }
    build(len,aa,ch,fa);
    build(len,bb,chh,faa);
    int flag=0;
    for (int i=1;i<=len;i++){
        if (fa[i]!=faa[i])flag=1;
        if (ch[i][0]!=chh[i][0])flag=1;
        if (ch[i][1]!=chh[i][1])flag=1;
        if (flag)break;
    }
    if (flag)return 0;
    else return 1;
}
 
int main(){
 int n;
  while(~scanf("%d",&n)){
     memset(stk,0,sizeof(stk));
   //  memset(aa,0,sizeof(aa));
     for (int i=1;i<=n;i++){
        scanf("%d",&aa[i]);
     }
     for (int i=1;i<=n;i++){
        scanf("%d",&bb[i]);
     }
     int l=1;
     int r=n;
     int ans=1;
      while(l<=r){
         int mid=(l+r)>>1;
         if(same(mid)){
            ans=mid;
            l=mid+1;
         }else {
            r=mid-1;
         }
      }
      printf("%d\n",ans);
  }
  return 0;
}

Method 2:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int stk[maxn],tp;
int aa[maxn],bb[maxn];
void build(int n,int a[],int ch[][2],int fa[]){
   tp=0;//Stack pointer
   for (int i=1;i<=n;i++)
   {
       int last=0;//Stack top element
       while(tp){
          if (a[stk[tp]]<=a[i]){//If the current value is greater than the top of the stack
            //If the right son of the top element of the stack exists now
            //The right son of the top element of the stack needs to be broken off from the left son of the new node.
            //At the same time, add the new node to the right son of the top element of the stack.
             if (ch[stk[tp]][1])ch[i][0]=ch[stk[tp]][1],fa[ch[stk[tp]][1]]=i;
             ch[stk[tp]][1]=i;fa[i]=stk[tp];
             break;
          }
          last=stk[tp--];//First remove the top element of the stack
       }
       //If the stack is empty, and last If it's worth it, add it to your left son.
       if (!tp && last)ch[i][0]=last,fa[last]=i;
       stk[++tp]=i;
   }
}
int fa[maxn],ch[maxn][2],faa[maxn],chh[maxn][2];
int main(){
 int n;
  while(~scanf("%d",&n)){
     memset(stk,0,sizeof(stk));
   //  memset(aa,0,sizeof(aa));
     for (int i=1;i<=n;i++){
        fa[i]=0;
        faa[i]=0;
        ch[i][0]=0;
        ch[i][1]=0;
        chh[i][0]=0;
        chh[i][1]=0;
     }
     for (int i=1;i<=n;i++){
        scanf("%d",&aa[i]);
     }
     for (int i=1;i<=n;i++){
        scanf("%d",&bb[i]);
     }
     int ans=1;
     build(n,aa,ch,fa);
     build(n,bb,chh,faa);
     int cnt=1;
     for (int i=2;i<=n;i++){
        if (ch[i][0]==chh[i][0])
          cnt++;
        else
          break;
     }
     printf("%d\n",cnt);
  }
  return 0;
}