아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

이중 대열

시간 제한3초메모리 제한512 MB

요약
각 열에서 두 병사의 자리를 바꿀지 정해 두 행 모두 같은 키가 없도록 만들 때, 필요한 최소 교환 횟수를 구한다.
난이도

보통10점 중 6점

유형
그래프, 유니온 파인드, 그리디
정답자
아직 제출이 없습니다

문제

2n2n명의 병사가 이중 대열로 서 있습니다. 두 개의 행이 있고 각 행에는 nn명의 병사가 있으므로, 각 열에는 두 명의 병사가 놓입니다.

각 행 안에서 같은 키를 가진 병사가 하나도 없을 때, 병사들이 올바르게 정렬되었다고 합니다.

한 번의 연산은 같은 열에 놓인(서로 다른 행에 있는) 두 병사를 맞바꾸는 것입니다. 병사들을 올바르게 정렬하기 위해 필요한 연산 횟수의 최솟값을 구하세요.

입력

첫째 줄에 정수 nn이 주어집니다 (1≤n≤500001 \le n \le 50000).

둘째 줄에는 nn개의 정수 x1,x2,…,xnx_1, x_2, \ldots, x_n이 공백으로 구분되어 주어집니다 (1≤xi≤1000001 \le x_i \le 100000). xix_i는 첫째 행 ii번째 병사의 키입니다.

셋째 줄에는 nn개의 정수 y1,y2,…,yny_1, y_2, \ldots, y_n이 공백으로 구분되어 주어집니다 (1≤yi≤1000001 \le y_i \le 100000). yiy_i는 둘째 행 ii번째 병사의 키입니다.

주어지는 모든 입력에 대해 병사들을 올바르게 정렬하는 것이 항상 가능함이 보장됩니다.

출력

병사들을 올바르게 정렬하기 위해 필요한 연산 횟수의 최솟값을 한 줄에 출력하세요.

힌트

아래 그림은 18명의 병사로 이루어진 이중 대열을 보여줍니다. 화살표는 병사들을 올바르게 정렬하는 교환을 나타냅니다.

예제1

  1. 예제 1

    입력
    9
    2 5 5 2 7 4 7 3 9
    1 6 8 4 6 3 9 1 8
    
    예상 출력
    3