만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

특별한 게임

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

요약
Dmytryk와 Petro가 1부터 2n까지 카드로 n라운드 게임을 할 때, 최적으로 플레이하면 Dmytryk가 이길 수 있는 최대 라운드 수를 구합니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

드미트릭과 페트로가 다음 게임을 한다. 값이 1부터 2n2n까지의 정수인 카드 2n2n장이 있으며, 모든 값은 서로 다르다. 게임을 시작할 때 각 플레이어는 정확히 nn장의 카드를 가진다.

전체 nn라운드가 진행되며, 첫 라운드의 선공은 드미트릭이다. 각 라운드에서 선공 플레이어는 자신의 카드 한 장을 낸다. 그다음 후공 플레이어가 선공의 카드를 보고 자신의 카드 한 장을 낸다. 값이 더 큰 카드를 낸 플레이어가 그 라운드에서 이기고, 다음 라운드의 선공이 된다. 그 뒤 두 카드는 게임에서 제외된다.

추가 규칙이 하나 있다. 각 라운드에서 후공 플레이어가 상대가 낸 카드보다 값이 큰 카드를 가지고 있다면, 그런 카드 중 한 장을 반드시 내야 한다.

각 플레이어의 목표는 자신이 이기는 라운드 수를 최대화하는 것이다. 두 플레이어가 최선을 다할 때 드미트릭이 이길 수 있는 라운드 수의 최댓값을 구하시오.

입력

첫 줄에 정수 nn (1≤n≤10001 \le n \le 1000)이 주어진다. 둘째 줄에는 드미트릭의 카드 nn개가, 셋째 줄에는 페트로의 카드 nn개가 주어진다.

출력

문제의 답을 출력한다.

예제2

  1. 예제 1

    입력
    3
    1 2 5
    3 4 6
    
    예상 출력
    1
    
  2. 예제 2

    입력
    2
    4 3
    1 2
    
    예상 출력
    2