시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB222100.000%

문제

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

You are allowed to perform zero or more operations on $a$ of the following kind:

Choose a contiguous subarray of even length and cyclically shift it by an even number of positions. Formally, you choose three integers $i, j$ and $k$ ($0 \leq i < j < k \leq n$, $j - i$ is even, $k - i$ is even) and $a$ becomes equal to $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 elements in the range of indices $[l,r)$ in 0-indexing and $(l,r]$ in 1-indexing.

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

입력

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$), elements of $a$.

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

출력

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

예제 입력 1

3
1 2 1
1 1 2


예제 출력 1

0


예제 입력 2

4
1 2 3 4
3 4 1 2


예제 출력 2

1


예제 입력 3

4
1 2 3 4
1 4 3 2


예제 출력 3

0