题目描述

小蓝有一个序列 a，同时他的朋友小乔有一个序列 b。 我们认为两个序列是和谐的，当且仅当存在某个数 x，使得对于所有的 i 有 a[i]+x=b[i]。 现在小蓝可以让序列 a 旋转，即通过一次参数为 k 的旋转可以将序列 a[1],a[2],...,a[n] 变为 a[1+k],a[2+k],...,a[n],a[1],a[2],...,a[k]。 小蓝希望知道，是否存在这样的旋转操作，能够让序列 a 和 b 是和谐的。 输出共一行，一个自然数 k 表示参数为 k 的旋转操作能够让 a,b 是和谐的，如果存在多个这样的 k，请输出最小的 k，如果不存在这样的 k，请输出 -1。

输入格式

输入的第一行包含一个正整数 n。 第二行包含 n 个正整数 a[1],a[2],...,a[n]，相邻整数之间使用一个空格分隔。 第三行包含 n 个正整数 b[1],b[2],...,b[n]，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案，如果不存在，请输出整数 -1。

样例

输入样例 1

4
2 3 4 5
2 3 4 1

输出样例 1

1

输入样例 2

5
1 2 3 4 5
2 3 4 5 6

输出样例 2

0

输入样例 3

8
1 2 1 2 1 2 1 2
3 4 3 4 3 4 3 4

输出样例 3

0

提示

数据范围：1≤n≤5×10^5，1≤a[i],b[i] ≤10^9。

样例说明：小蓝可以让序列 a 旋转得到 3 4 5 2，根据和谐序列的定义，令 x=-1，那么此时 a,b 就是和谐的。

思路：KMP 算法 由题意得 x= （b序列和 - a序列和）/n。 若 x 不为整数，显然不可能。 若 x 为整数，构造出序列 a 的目标序列，记为 d（di=bi-x）。 若 a 能旋转成为 d，则 d 必为 a 重复一遍所得序列（即将 a 接在 a 末尾形成的序列 s）的连续子序列，KMP 在 s 中匹配 d 即可。 找到第一个符合条件的位置，输出就可以退出了。一个都未找到要输出 -1。