qsgg and Permutation
题号:NC253366
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定两个长度为 n 的排列 AB

每次操作可以将 A 中的一个元素插入到任意位置(可以插到最前,最后或两个数之间)。

求最少操作使得 A=B

输入描述:

输入共 3 行。

第一行一个整数 n \ (1≤n≤ 10^6)

第二行 n 个整数 A_i (1≤A_i≤n) 表示排列 A

第三行 n 个整数 B_i (1≤B_i≤n) 表示排列 B

输出描述:

输出一个整数,表示最少操作次数。
示例1

输入

复制
6
6 1 2 3 4 5
1 2 4 3 5 6

输出

复制
2

说明

第一步,将 6 插到最后,[6,1,2,3,4,5] \rightarrow [1,2,3,4,5,6]
第二步,将 4 插到 23 之间,[1,2,3,4,5,6] \rightarrow [1,2,4,3,5,6]
可以证明没有更少的操作次数使得 A = B