Algorithm Class - Selection Sort 5

Time limit1sMemory limit512 MB

Summary

Given two arrays of N distinct integers, decide whether array A equals array B at some moment during selection sort, counting the initial state.

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

Problem

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

There is an array A holding N distinct positive integers. When array A is sorted in ascending order with selection sort, determine 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.

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 value 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 ≤ 10,000).

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

The next line gives the distinct elements of array B, B1, B2, ..., BN (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
```