Algorithm Class - Insertion Sort 3

Seojun is again working as a teaching assistant for the insertion sort class. 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 insertion sort, check whether array A ever equals 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 insertion sort on an array of size N is as follows.

insertion_sort(A[1..N]) { # sorts A[1..N] in ascending order
    for i <- 2 to N {
        loc = i - 1;
        newItem = A[i];

        # at this point A[1..i-1] is already sorted
        while (1 <= loc and newItem < A[loc]) {
            A[loc + 1] <- A[loc];
            loc--;
        }
        if (loc + 1 != i) then A[loc + 1] = newItem;
    }
}

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

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

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

Print 1 if array A equals array B at some point while insertion sort sorts array A in ascending order, and 0 otherwise.