알고리즘 수업 - 삽입 정렬 6

서준이는 오늘도 삽입 정렬 수업의 조교를 맡고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제로 확인해 보자.

$N$개의 서로 다른 양의 정수가 저장된 배열 $A$가 있다. 삽입 정렬로 $A$를 오름차순 정렬할 때, 정렬 과정에서 $A$가 배열 $B$와 같아지는 경우가 발생하는지 확인해 보자. 초기 상태의 $A$도 정렬 과정에서 나올 수 있는 상태로 본다.

$N$이 매우 커서 시간 초과를 걱정하고 있는 서준이를 도와주자.

크기가 $N$인 배열에 대한 삽입 정렬 의사 코드는 다음과 같다.

insertion_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for i <- 2 to N {
        loc = i - 1;
        newItem = A[i];

        # 이 지점에서 A[1..i-1]은 이미 정렬되어 있는 상태
        while (1 ≤ loc and newItem < A[loc]) {
            A[loc + 1] <- A[loc];
            loc--;
        }
        if (loc + 1 != i) then A[loc + 1] = newItem;
    }
}

첫째 줄에 배열 $A$, $B$의 크기 $N$($5 \le N \le 500000$)이 주어진다.

다음 줄에 서로 다른 배열 $A$의 원소 $A_1, A_2, \ldots, A_N$이 주어진다. ($1 \le A_i \le 10^9$)

다음 줄에 배열 $B$의 원소 $B_1, B_2, \ldots, B_N$이 주어진다. ($1 \le B_i \le 10^9$)

삽입 정렬로 배열 $A$를 오름차순 정렬하는 과정에서 배열 $A$가 배열 $B$와 같은 경우가 발생하면 1, 아니면 0을 출력한다.