높은 카드가 이긴다

면접 대비

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

요약

엘시가 순서대로 내는 카드를 보고 베시가 가진 N장 카드를 각 라운드에 배치해 더 높은 카드로 이기는 횟수를 최대로 만듭니다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

소 베시는 카드 게임을 아주 좋아한다. 마주 보는 엄지가 없다는 점을 생각하면 꽤 놀라운 취미다. 문제는 무리의 다른 소가 하나같이 형편없는 상대라는 것이다. 얼마나 형편없냐면, 카드를 내는 순서가 언제나 완전히 예측된다. 그래도 베시가 이기는 방법을 찾아내는 일은 여전히 만만치 않다.

베시와 친구 엘시는 간단한 카드 게임을 한다. $1$ 번부터 $2N$ 번까지 번호가 붙은 카드 $2N$ 장을 베시가 $N$ 장, 엘시가 $N$ 장씩 나눠 갖는다. 두 소는 $N$ 번의 라운드를 치르고, 각 라운드에서 카드를 한 장씩 낸다. 그 라운드에 더 큰 번호를 낸 쪽이 $1$ 점을 얻는다.

엘시가 카드를 내는 순서를 베시가 미리 알고 있을 때, 베시가 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫째 줄에 $N$ 이 주어진다. ( $1 \le N \le 50000$ )

다음 $N$ 개의 줄에는 엘시가 각 라운드에서 낼 카드가 순서대로 한 줄에 하나씩 주어진다. 카드 번호는 모두 서로 다르고 $1$ 이상 $2N$ 이하다. 나머지 $N$ 장이 곧 베시의 카드이므로, 이 정보만으로 베시의 손패도 알 수 있다.

출력

베시가 얻을 수 있는 최대 점수를 한 줄에 출력한다.

힌트

예제에서 엘시의 카드는 $1$ , $6$ , $4$ 이므로 베시의 카드는 $2$ , $3$ , $5$ 다. $5$ 를 마지막 라운드까지 아껴 두었다가 엘시의 $4$ 를 이기면 $2$ 점을 얻고, 그보다 더 얻을 수는 없다.

예제6

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