← 返回题目列表

Codeforces · 67/D

D. 光学实验

中文机器翻译题面 查看原题

Phunsuk Wangdu教授对射线进行了一些实验。 n 条射线的设置如下。

有一个矩形盒子,其相对面上正好有 n 个孔。所有光线都从盒子第一面的孔进入并从盒子另一面的孔射出。每个孔只能有一条光线进入或退出。这些孔在一条直线上。

王都教授正在给学生们展示他的实验。他表明,在某些情况下,所有光线都与其他光线相交。一位好奇的学生问教授:“先生,有一些光线组,该组中的所有光线都与该组中的所有其他光线相交。我们可以确定最大的一组光线中的光线数量吗?”。

旺都教授现在遇到了麻烦,知道你的智力,他请求你帮助他。

输入

第一行包含 n (1 ≤ n ≤ 106),光线数量。第二行包含 n 个不同的整数。第 i 个整数 xi (1 ≤ xi ≤ n) 表示第 xi 条射线从第 i 个孔进入。类似地,第三行包含 n 个不同的整数。第 i 个整数 yi (1 ≤ yi ≤ n) 表示第 yi 条光线从第 i 个孔中射出。所有光线均从 1 到 n 编号。

输出

输出包含唯一的整数,它是最大光线组中所有彼此相交的光线数量。

示例

输入 #1

5
1 4 5 2 3
3 4 2 1 5

输出 #1

3

输入 #2

3
3 1 2
2 3 1

输出 #2

2

注意

对于第一个测试用例,如图所示。第一个测试用例的输出是 3,因为编号 1、4 和 3 的光线是彼此相交的光线,即 1 与 4 和 3 相交,3 与 4 和 1 相交,4 与 1 和 3 相交。因此,该组中的每条光线都彼此相交。不存在任何包含超过 3 条光线的群满足上述约束。