Algorithm Class - Bubble Sort 3

Seojun is again working as a teaching assistant for the bubble sort class. Let us check through 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 bubble 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 bubble sort on an array of size N is as follows.

bubble_sort(A[1..N]) { # sorts A[1..N] in ascending order
    for last <- N downto 2
        for i <- 1 to last - 1
            if (A[i] > A[i + 1]) then A[i] <-> A[i + 1]  # swap elements
}

The first line gives the size N 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)

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