Algorithm Class - Quick Sort 3

Seojun is once again a teaching assistant for the quick 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. We want to check whether, while sorting A in ascending order with quick sort, the array A ever becomes equal to array B. The initial state of array A also counts as one of the states that can occur during the sort.

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

quick_sort(A[p..r]) { # sorts A[p..r] in ascending order
    if (p < r) then {
        q <- partition(A, p, r);  # partition
        quick_sort(A, p, q - 1);  # sort the left subarray
        quick_sort(A, q + 1, r);  # sort the right subarray
    }
}

partition(A[], p, r) {
    x <- A[r];    # pivot
    i <- p - 1;   # i is the end point of the elements less than or equal to x
    for j <- p to r - 1  # j is the start point of the elements not yet placed
        if (A[j] ≤ x) then A[++i] <-> A[j]; # increment i, then swap A[i] <-> A[j]
    if (i + 1 != r) then A[i + 1] <-> A[r]; # if i + 1 and r differ, swap A[i + 1] and A[r]
    return i + 1;
}

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

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. (1 ≤ Bi ≤ 109)

Print 1 if, while sorting array A in ascending order with quick sort, array A ever becomes equal to array B; otherwise print 0.