책 배열

실행 시간 제한	메모리 제한
2 초	1024 MB

📃 해결할 문제

대학교 도서관에서, 도서관 사서인 지니는 책들을 새로운 순서로 배열하려고 합니다. 현재 $N$ 권의 책이 있습니다. ( $1 \le N \le 10^5$ ) 이 책들은 편리하게도 $1 \ldots N$ 까지 번호가 매겨져 있습니다.

처음에는 책들이 $a_1,a_2, \ldots,a_N$ 순서로 왼쪽에서 오른쪽으로 배열되어 있습니다. 지니의 목표는 책들을 $b_1, \ldots,b_N$ 순서로 왼쪽에서 오른쪽으로 배열하는 것입니다. 이를 달성하기 위해 그는 일련의 수정을 책 배열에 수행할 수 있습니다. 각 수정은 단일 책을 선택하고 그것을 왼쪽으로 몇 개의 위치로 이동하는 것으로 구성됩니다.

지니가 원하는 순서대로 책을 배열하기 위해 필요한 최소 수정 횟수를 계산해주세요.

💻 입력

첫 번째 입력 줄에는 $N$ 이 포함됩니다. 두 번째 줄에는 $a_1,a_2, \ldots,a_N$ 이 포함되어 있습니다. 세 번째 줄에는 $b_1,b_2, \ldots,b_N$ 이 포함되어 있습니다.

🖨️ 출력

지니가 원하는 순서를 생성하기 위해 필요한 최소 수정 횟수를 출력하십시오.

💻 예제 입력 1

5
1 2 3 4 5
1 2 3 4 5

🖨️ 예제 출력 1

💻 예제 입력 2

5
5 1 3 2 4
4 5 2 1 3

🖨️ 예제 출력 2

💡 힌트

예시 입력:

5
5 1 3 2 4
4 5 2 1 3

예시 출력 :

이 예제에서는 두 번의 수정이면 충분합니다. 지니가 책을 재배열하는 한 가지 방법은 다음과 같습니다:

책 $4$ 를 선택하고 왼쪽으로 네 위치 이동합니다.
책 $2$ 를 선택하고 왼쪽으로 두 위치 이동합니다.

5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3

점수 :

테스트 케이스 3-6은 $N \le 100$ 을 만족합니다.
테스트 케이스 7-10은 $N \le 5000$ 을 만족합니다.
테스트 케이스 11-14는 추가적인 제약 조건을 만족하지 않습니다.

출처: USACO 2022 February Contest, Bronze Problem 2. Photoshoot 2