#P1365C. Rotation Matching
Rotation Matching
No submission language available for this problem.
Description
After the mysterious disappearance of Ashish, his two favourite disciples Ishika and Hriday, were each left with one half of a secret message. These messages can each be represented by a permutation of size . Let's call them and .
Note that a permutation of elements is a sequence of numbers , in which every number from to appears exactly once.
The message can be decoded by an arrangement of sequence and , such that the number of matching pairs of elements between them is maximum. A pair of elements and is said to match if:
- , that is, they are at the same index.
His two disciples are allowed to perform the following operation any number of times:
- choose a number and cyclically shift one of the permutations to the left or right times.
A single cyclic shift to the left on any permutation is an operation that sets simultaneously. Likewise, a single cyclic shift to the right on any permutation is an operation that sets simultaneously.
Help Ishika and Hriday find the maximum number of pairs of elements that match after performing the operation any (possibly zero) number of times.
The first line of the input contains a single integer — the size of the arrays.
The second line contains integers , , ..., — the elements of the first permutation.
The third line contains integers , , ..., — the elements of the second permutation.
Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.
Input
The first line of the input contains a single integer — the size of the arrays.
The second line contains integers , , ..., — the elements of the first permutation.
The third line contains integers , , ..., — the elements of the second permutation.
Output
Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.
Samples
Note
For the first case: can be shifted to the right by . The resulting permutations will be and .
For the second case: The operation is not required. For all possible rotations of and , the number of matching pairs won't exceed .
For the third case: can be shifted to the left by . The resulting permutations will be and . Positions and have matching pairs of elements. For all possible rotations of and , the number of matching pairs won't exceed .