Algorithm Class - Selection Sort 6

Interview

Time limit3sMemory limit512 MB

Summary

Given distinct arrays A and B, decide whether A equals B at some moment during selection sort, including before any swap.

Level: Medium6 of 10
Topics: Sorting, Implementation, Array, Simulation
Solved: No attempts yet

Problem

Seojun is working as a teaching assistant for the selection sort class again today. Let us check through a problem whether the students understood what his father taught in class.

There is an array A holding N distinct positive integers. When array A is sorted in ascending order with selection sort, check whether array A ever becomes equal to array B during the sorting process. The initial state of array A also counts as a state that can occur during sorting.

Help our Seojun, who is worrying about a time limit because N is very large.

The pseudocode for selection sort on an array of size N is as follows.

selection_sort(A[1..N]) { # sort A[1..N] in ascending order
    for last <- N downto 2 {
        find the largest number A[i] among A[1..last]
        if (last != i) then A[last] <-> A[i]  # if last and i differ, swap A[last] and A[i]
    }
}

Input

The first line gives N, the size of arrays A and B (5 ≤ N ≤ 500,000).

The next line gives the elements of array A, A1, A2, ..., AN, which are all distinct. (1 ≤ Ai ≤ 109)

The next line gives the elements of array B, B1, B2, ..., BN, which are all distinct. (1 ≤ Bi ≤ 109)

Output

Print 1 if array A becomes equal to array B at some point while selection sort sorts array A in ascending order, and 0 otherwise.

Examples2

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