C. Rotation Matching

C. Rotation Matching

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 nn. Let's call them aa and bb.

Note that a permutation of nn elements is a sequence of numbers a1,a2,…,ana1,a2,…,an, in which every number from 11 to nn appears exactly once.

The message can be decoded by an arrangement of sequence aa and bb, such that the number of matching pairs of elements between them is maximum. A pair of elements aiai and bjbj is said to match if:

• i=ji=j, that is, they are at the same index.
• ai=bjai=bj

His two disciples are allowed to perform the following operation any number of times:

• choose a number kk and cyclically shift one of the permutations to the left or right kk times.

A single cyclic shift to the left on any permutation cc is an operation that sets c1:=c2,c2:=c3,…,cn:=c1c1:=c2,c2:=c3,…,cn:=c1 simultaneously. Likewise, a single cyclic shift to the right on any permutation cc is an operation that sets c1:=cn,c2:=c1,…,cn:=cn−1c1:=cn,c2:=c1,…,cn:=cn−1 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.

Input

The first line of the input contains a single integer nn (1≤n≤2⋅105)(1≤n≤2⋅105) — the size of the arrays.

The second line contains nn integers a1a1, a2a2, ..., anan (1≤ai≤n)(1≤ai≤n) — the elements of the first permutation.

The third line contains nn integers b1b1, b2b2, ..., bnbn (1≤bi≤n)(1≤bi≤n) — 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.

Examples

input

Copy

5
1 2 3 4 5
2 3 4 5 1

output

Copy

5

input

Copy

5
5 4 3 2 1
1 2 3 4 5

output

Copy

1

input

Copy

4
1 3 2 4
4 2 3 1

output

Copy

2

Note

For the first case: bb can be shifted to the right by k=1k=1. The resulting permutations will be {1,2,3,4,5}{1,2,3,4,5} and {1,2,3,4,5}{1,2,3,4,5}.

For the second case: The operation is not required. For all possible rotations of aa and bb, the number of matching pairs won't exceed 11.

For the third case: bb can be shifted to the left by k=1k=1. The resulting permutations will be {1,3,2,4}{1,3,2,4} and {2,3,1,4}{2,3,1,4}. Positions 22 and 44 have matching pairs of elements. For all possible rotations of aa and bb, the number of matching pairs won't exceed 22.

=========================================================================

只对b进行平移是可以的，只对b进行右移也是可以的，那么就统计出来每个数字偏移的距离即可

取其最大值

#include
#include
#include
# include
 
#include
#define  mo 998244353;
using namespace std;
 
typedef long long int ll;
 
int pre[200000+10];
int now[200000+10];
int cnt[200000+10];
int main()
{
 
    int n;
 
    cin>>n;
 
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        pre[x]=i;
    }
 
    for(int i=1;i<=n;i++)
    {
        cin>>now[i];
 
        if(i-pre[now[i]]>=0)
        {
            cnt[i-pre[now[i]]]++;
        }
        else
        {
            cnt[i-pre[now[i]]+n]++;
        }
    }
 
    int ans=0;
 
    for(int i=0;i<=n;i++)
    {
        ans=max(ans,cnt[i]);
    }
 
    cout<
 
 
 
    return 0;
}