문제
농부 존은 멋진 사진을 찍기 위해 1…N(1≤N≤105)으로 번호가 매겨진 N마리의 소를 줄지어 세웠다.
처음에 소는 왼쪽에서 오른쪽으로 a1, a2, …, aN 순서로 배치된다.
농부 존의 목표는 왼쪽에서 오른쪽으로 b1, b2, …, bN 순서로 소를 배열하는 것이다.
이를 위해 일련의 수정 작업을 수행할 수 있는데, 각 수정 작업은 한 마리의 소를 왼쪽으로 일정 칸의 위치 이동하는 것이다.
농부 존이 소를 원하는 순서로 배열하는 데 필요한 최소 수정 횟수를 출력하는 프로그램을 작성하시오.
[부분문제]
테스트 케이스 1-6: N≤100.
테스트 케이스 7-10: N≤5000.
테스트 케이스 11-14: N≤100000.
입력
첫 번째 줄에는 N이 입력된다.
두 번째 줄에는 a1, a2, …, aN이 입력된다.
세 번째 줄에는 b1, b2, …, bN이 입력된다.
출력
소를 원하는 순서로 정렬하는 데 필요한 최소 수정 횟수를 출력하시오.
예제1
입력
5
1 2 3 4 5
1 2 3 4 5
출력
0
예제2
입력
5
5 1 3 2 4
4 5 2 1 3
출력
2
힌트
출처
USACO 2022 February Bronze