【问题描述】 Captain正在精心构造两个序列并且让它们相似。我们令两个长度为n的序列u、v为相似的,当且仅当对于所有的1<=l<=r<=n,满足RMQ(u,l,r)=RMQ(v,l,r),其中RMQ(u,l,r)表示u序列中l到r这段区间的最小值所处的位置。那么相应的,captain构造出的序列中所有元素都是不相同的,但是有个小孩过来捣乱,他将两个序列后面分别添加了一些元素使得他们变成了两个排列。Captain非常生气,他想找回原来的序列,但是如果求出原来的序列最长能是多少就更好了。简要题意:给定两个排列A和B,求出它们的最大前缀p,满足a1,a2…ap、b1,b2…bp两个序列相似。
【输入描述】第一行一个整数n代表A、B数列的长度。第二行n个整数表示A序列。第三行n个整数表示B序列。数据保证A和B分别为两个1-n排列。
【输出描述】一行一个整数表示最大前缀长度p。
【样例输入】
[样例1]32 1 33 1 2
[样例2]53 1 5 2 45 2 4 3 1
【样例输出】
[样例1]3
[样例2]4
【数据范围】
对于20%的测试数据,n<=200
对于40%的测试数据,n<=2000
对于80%的测试数据,n<=100000
对于100%的测试数据,n<=500000