← 返回题目列表

Codeforces · 1365/C

C. 旋转匹配

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

阿什什神秘失踪后,他最喜欢的两个弟子伊什卡和赫里迪分别留下了一半的秘密信息。这些消息均可以由大小为 $$$n$$$ 的排列表示。我们称它们为$$$a$$$ 和$$$b$$$。

请注意,$$$n$$$ 元素的排列是数字 $$$a_1, a_2, \ldots, a_n$$$ 的序列,其中从 $$$1$$$ 到 $$$n$$$ 的每个数字都恰好出现一次。

消息可以通过序列$$$a$$$和$$$b$$$的排列来解码,使得它们之间的匹配元素对的数量最大。如果满足以下条件,则称一对元素 $$$a_i$$$ 和 $$$b_j$$$ 匹配:

- $$$i = j$$$,也就是说,它们位于相同的索引处。
- $$$a_i = b_j$$$

他的两个弟子可以执行任意次数的以下操作:

- 选择一个数字 $$$k$$$ 并将其中一个排列向左或向右循环移动 $$$k$$$ 次。

任何排列 $$$c$$$ 上的单个循环左移是同时设置 $$$c_1:=c_2, c_2:=c_3, \ldots, c_n:=c_1$$$ 的操作。同样,在任何排列 $$$c$$$ 上向右单个循环移位是同时设置 $$$c_1:=c_n, c_2:=c_1, \ldots, c_n:=c_{n-1}$$$ 的操作。

帮助 Ishika 和 Hriday 找到执行任意(可能为零)次操作后匹配的元素对的最大数量。

输入

输入的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le n)$$$ — 第一个排列的元素。

第三行包含 $$$n$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ $$$(1 \le b_i \le n)$$$ — 第二个排列的元素。

输出

执行上述操作几次(可能为零)后,打印元素匹配对的最大数量。

示例

输入 #1

5
1 2 3 4 5
2 3 4 5 1

输出 #1

5

输入 #2

5
5 4 3 2 1
1 2 3 4 5

输出 #2

1

输入 #3

4
1 3 2 4
4 2 3 1

输出 #3

2

注意

对于第一种情况:$$$b$$$ 可以向右移动 $$$k = 1$$$。生成的排列将是 $$$\{1, 2, 3, 4, 5\}$$$ 和 $$$\{1, 2, 3, 4, 5\}$$$。

对于第二种情况:不需要操作。对于 $$$a$$$ 和 $$$b$$$ 的所有可能旋转,匹配对的数量不会超过 $$$1$$$。

对于第三种情况:$$$b$$$ 可以向左移动 $$$k = 1$$$。生成的排列将是 $$$\{1, 3, 2, 4\}$$$ 和 $$$\{2, 3, 1, 4\}$$$。位置 $$$2$$$ 和 $$$4$$$ 具有匹配的元素对。对于 $$$a$$$ 和 $$$b$$$ 的所有可能旋转,匹配对的数量不会超过 $$$2$$$。