给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。
注意：
第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。
输入格式
第一行包含一个整数 n。
接下来两行，每行包含 n 个整数，表示一个整数序列。
输出格式
输出一个整数，表示最长公共子序列的长度。
数据范围
1≤n≤106,
序列内元素取值范围 [1,106]。
样例
输入样例1：
5
1 2 3 4 5
1 2 3 4 5
输出样例1：
5
输入样例2：
5
1 2 3 5 4
1 2 3 4 5
输出样例2：
4
package main
import "fmt"
const N=1000110
var(
id[N]int
q[N]int
)
func max(a,b int)int{
if a > b{
return a
}
return b
}
func main(){
var n,len,x int
fmt.Scanf("%d",&n)
for i:= 0; i < 1000110; i ++ {
id[i] = -1
}
for i:= 0; i < n; i ++ {
fmt.Scanf("%d",&x)
id[x] = i
}
len = 0
q[0] = -1
for i:= 0; i < n; i ++{
var x,k,l,r int
fmt.Scanf("%d",&x)
k = id[x]
if k==-1{
continue
}
l=0
r=len
for {
if l<r{
var mid int
mid=(l+r+1)>>1
if q[mid]<k{
l=mid
}else {
r=mid-1
}
}else {
break;
}
}
q[r+1]=k
len=max(len,r+1)
}
fmt.Println(len)
}
