소가 길을 건너간 이유 10

소가 왜 길을 건너는지는 아직 풀리지 않은 난제지만, 농부 존의 소들이 길을 자주 건넌다는 사실은 잘 알려져 있다. 소들이 길을 너무 자주 건너서 건너는 도중에 서로 부딪히는 일도 생기는데, 존은 이 문제를 해결하고 싶다.

농장에는 곧게 뻗은 길이 하나 있고, 길 양쪽에 목초지가 $N$개씩 있다 ($1 \le N \le 100\,000$). 종마다 목초지 구조가 크게 달라서 한 목초지에는 정해진 종의 소만 방목할 수 있다. 즉 $i$번 목초지에는 $i$번 소만 방목할 수 있다. 소가 길을 건널 때는 길 반대편에서 자신의 종을 방목하는 목초지로 이동한다.

존이 목초지를 지을 때 신경을 쓰지 않은 탓에 목초지 순서가 뒤죽박죽이어서, $a$종 소와 $b$종 소가 건너는 경로가 서로 교차할 수도 있다. 이런 $(a, b)$를 "가로지르는 쌍"이라고 하자.

존은 가로지르는 쌍의 수를 줄이려고 농장을 옮기는 방법을 생각해 냈다. $0 \le k < N$인 정수 $k$를 하나 골라, 한쪽 길가에서 맨 뒤에 있는 목초지 $k$개를 순서를 유지한 채 맨 앞으로 옮긴다. 예를 들어 목초지 번호가 차례대로 3, 7, 1, 2, 5, 4, 6이고 $k=2$라면 옮긴 뒤의 목초지 번호는 4, 6, 3, 7, 1, 2, 5가 된다. 옮기는 쪽은 길의 왼쪽이어도 되고 오른쪽이어도 되지만, 둘 중 한쪽만 옮길 수 있다.

가로지르는 쌍의 수가 가장 적어지도록 존을 도와주자.

첫째 줄에 $N$이 주어진다. 다음 $N$개의 줄에는 길 왼쪽에 있는 목초지 번호가 차례대로 하나씩 주어진다. 각 종은 정확히 한 번씩 나타난다. 그다음 $N$개의 줄에는 길 오른쪽에 있는 목초지 번호가 같은 방식으로 주어진다.

가로지르는 쌍의 최소 개수를 출력한다.