<span>Magic Stones CodeForces - 1110E （思维+差分）</span>

Grigory has

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index

Andrew, Grigory's friend, also has

Input

The first line contains one integer

The second line contains integers

Output

If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print "Yes".

Otherwise, print "No".

Examples

input

Copy

4
7 2 4 12
7 15 10 12

output

Copy

Yes

input

Copy

3
4 4 4
1 2 3

output

Copy

No

Note

In the first example, we can perform the following synchronizations (

First, synchronize the third stone
Then synchronize the second stone:

In the second example, any operation with the second stone will not change its charge

思路：

通过样例观察：

In the first example, we can perform the following synchronizations (

First, synchronize the third stone
Then synchronize the second stone:

我们来看最初的数组，和中途的数组，以及目标数组，他们的差分都是【5，8，2】这三个数，变来变去都是这三个，

再加以观察可以发现，我们每执行一个操作，影响的只是交换了差分，那么只需要数组的首尾两个数相等，并且中间的差分数排序后相等即可保证一一定能交换成功。

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define rt return
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
int a[maxn];
int b[maxn];
int main()
{
    gbtb;
    cin>>n;
    repd(i,1,n)
    {
        cin>>a[i];
    }
    repd(i,1,n)
    {
        cin>>b[i];
    }
    
    
    std::vector<int> v1;
    std::vector<int> v2;
    bool isok=1;
    if(a[1]!=b[1]||a[n]!=b[n])
    {
        // db(2);
        isok=0;
    }
    
    repd(i,2,n)
    {
        v1.pb(a[i]-a[i-1]);
        v2.pb(b[i]-b[i-1]);
    }
    int z=sz(v1);
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    repd(i,0,z-1)
    {
        if(v1[i]!=v2[i])
        {
            isok=0;
        }
    }
    if(isok)
    {
        printf("Yes\n");
    }else
    {
        printf("No\n");
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}