Two arrays u and v each with m distinct elements are called equivalent if and only if RMQ(u,l,r)=RMQ(v,l,r)RMQ(u,l,r)=RMQ(v,l,r) for all 1≤l≤r≤m1≤l≤r≤m
where RMQ(w,l,r)RMQ(w,l,r) denotes the index of the minimum element among wl,wl+1,…,wrwl,wl+1,…,wr.
Since the array contains distinct elements, the definition of minimum is unambiguous.

Bobo has two arrays a and b each with n distinct elements. Find the maximum number p≤np≤n where {a1,a2,…,ap}{a1,a2,…,ap} and {b1,b2,…,bp}{b1,b2,…,bp} are equivalent.

输入描述: 

The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,ana1,a2,…,an.
The third line contains n integers b1,b2,…,bnb1,b2,…,bn.
* 1≤n≤1051≤n≤105 * 1≤ai,bi≤n1≤ai,bi≤n * {a1,a2,…,an}{a1,a2,…,an} are distinct.
* {b1,b2,…,bn}{b1,b2,…,bn} are distinct.
* The sum of n does not exceed 5×1055×105.

输出描述: 

For each test case, print an integer which denotes the result.
题意大概就是两个数组，找最大的p，使对于1到p的所有子区间都保证最小值的下标相同；
这时我们就可以发现，如果a[i]<a[i+1]&&b[i]<b[i+1]，则a[i+1]和b[i+1]对之前所有子区间都不构成影响，因为总有min（a[1]，a[i]）比a[i+1]小；
那么我们可以线性的考虑，对于a[i]<a[i+1]&&b[i]<b[i+1]这种情况直接跳过，其他的情况则往前寻找第一个比a[i](b[i])小的数，如果下标相等则符合；如果下标不等则说明了不能取，证明如下：
设往前寻找第一个比a[i]小的数的下标为k1，同理b为k2，如果k1！=k2，则在（min（k1,k2），i）这个子区间上不成立，反正成立（都推到i了，则前面的肯定经过了一样的推理证明成立，可知所有子区间均成立）
找前面的第一个比自身小的数可以用单调栈的思想来标记（由于某人不会，我粗略说一下这题的用法），每次找到当前项符合的值，记录下标，到下次往前找的时候可以直接跳到这一项的符合值；
比如设当前为第k项，找到了第m项是符合的，则下次第i项（i>k）往前搜索搜到k时可直接跳到第m项。
代码如下： 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3fffffff
#define maxn 100005
int n,m,k,t;
int a[maxn],b[maxn],num1[maxn],num2[maxn];
int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        a[0]=b[0]=0;
        num1[1]=num2[1]=0;
        for(int i=2;i<=n;i++){
            int k1=i-1,k2=i-1;
            while(a[i]<a[k1])
                k1=num1[k1];
            num1[i]=k1;
            while(b[i]<b[k2])
                k2=num2[k2];
            num2[i]=k2;
            if(num1[i]!=num2[i]){
                printf("%d\n",i-1);
                break;
            }
            if(i==n)
                printf("%d\n",n);
        }
    }
}