Formally, You Choose Three Integers

Time limit2sMemory limit512 MB

Summary

Decide whether array a can be turned into array b by repeatedly cyclically shifting an even-length contiguous block by an even number of positions.

Level: Hard8 of 10
Topics: Math, Array, Combinatorics, Sorting
Solved: No attempts yet

Problem

You are given two arrays $a$ and $b$ of the same length $n$ .

You may perform the following operation on $a$ zero or more times:

Choose a contiguous subarray of even length and cyclically shift it by an even number of positions. Formally, you choose three integers $i, j, k$ ( $0 \leq i < j < k \leq n$ , $j - i$ is even, $k - i$ is even) and $a$ becomes $a_{0:i} + a_{j:k} + a_{i:j} + a_{k:n}$ , where $a_{l:r}$ denotes a slice with Python indexing. Precisely, it contains the elements with indices in the range $[l,r)$ in 0-indexing and $(l,r]$ in 1-indexing.

Is it possible to transform $a$ into $b$ ?

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 3 \cdot 10^5$ ), the length of $a$ and $b$ .

The second line contains $n$ integers $a_i$ ( $1 \leq a_i \leq n$ ), the elements of $a$ .

The third line contains $n$ integers $b_i$ ( $1 \leq b_i \leq n$ ), the elements of $b$ .

Output

Print 1 if it is possible to transform $s$ into $t$ , and 0 otherwise.

Examples3

Example 1
Input
```
3
1 2 1
1 1 2
```
Expected output
```
0
```
Example 2
Input
```
4
1 2 3 4
3 4 1 2
```
Expected output
```
1
```
Example 3
Input
```
4
1 2 3 4
1 4 3 2
```
Expected output
```
0
```