给定一个序列 A 和一个目标序列 B,序列中的每个元素互不相同,每次操作可以选定一组 i,j,满足 j−i=k 且 k 为正整数,交换 ai,aj。
保证 A=B,保证经过排序后的 A,B 相等。
请你求出所有的 k 使得 A 可以经过若干次操作变为 B。
给定一个序列 A 和一个目标序列 B,序列中的每个元素互不相同,每次操作可以选定一组 i,j,满足 j−i=k 且 k 为正整数,交换 ai,aj。
保证 A=B,保证经过排序后的 A,B 相等。
请你求出所有的 k 使得 A 可以经过若干次操作变为 B。
若有 m 个满足要求的整数 k,请输出 m 行,每行一个正整数。
请按照升序输出所有满足要求的 k。
样例1
5
1 2 3 4 5
1 2 3 5 4
样例2
5
1 2 3 5 4
1 3 4 2 5
样例3
5
1 4 3 2 5
1 2 3 4 5
样例1
1
样例2
1
样例3
1
2
子任务编号
n
特殊性质
分值
1
≤7
无
10
2
≤2000
无
20
3
≤2×10^5
a
30
4
≤2×10^5
无
40
特殊性质 a:A 与 B 仅两个元素位置不同
对于 100% 的数据,满足 3≤n≤2×10^5,1≤Ai,Bi≤10^9。