높은카드, 낮은카드(High Card Low Card)

암소 베시는 카드 게임의 엄청난 팬입니다. 소에게는 카드를 쥘 수 있는 엄지손가락이 없다는 점을 고려하면 꽤 놀라운 일이죠.

불행히도 무리 중 어떤 소도 베시의 좋은 상대가 되지 못합니다. 사실 다른 소들은 게임을 너무 못해서 항상 완벽하게 예측 가능한 방식으로만 카드를 냅니다!

그럼에도 불구하고, 베시가 이길 방법을 찾아내는 것은 여전히 까다로운 일일 수 있습니다.

베시와 그녀의 친구 엘시는 현재 1부터 2N까지 번호가 매겨진 2N장의 카드를 사용하는 간단한 카드 게임을 하고 있습니다. 카드를 베시가 N장, 엘시가 N장씩 나누어 가집니다.

그런 다음 두 소는 N번의 라운드를 진행하며, 각 라운드마다 베시와 엘시는 각각 한 장의 카드를 냅니다.

처음 N/2번의 라운드에서는 더 높은 숫자의 카드를 낸 플레이어가 1점을 얻고, 마지막 N/2번의 라운드에서는 규칙이 바뀌어 더 낮은 숫자의 카드를 낸 플레이어가 1점을 얻습니다.

베시가 엘시가 낼 카드의 순서를 미리 완벽하게 예측할 수 있다고 할 때, 베시가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 N의 값이 주어집니다. (2 ≤ N ≤ 50,000, N은 짝수)

다음 N개의 줄에는 엘시가 각 라운드에서 차례대로 낼 카드의 번호가 주어집니다. 이 정보를 바탕으로 베시가 가진 카드가 무엇인지 쉽게 알아낼 수 있습니다.

출력

베시가 얻을 수 있는 최대 점수를 하나의 정수로 출력합니다.

예제 입력 1

4
1
8
4
3

예제 출력 1

2

힌트

입력을 통해 엘시가 1, 8, 4, 3번 카드를 낼 것임을 알 수 있으므로, 베시의 손에는 반드시 남은 카드인 2, 5, 6, 7번 카드가 있어야 합니다.

베시는 게임의 후반부(낮은 카드가 이기는 라운드) 중 하나에서 쓰기 위해 가장 낮은 '2'번 카드를 아껴둠으로써 최대 2점을 얻을 수 있습니다.

출처

USACO 2015 December Contest, Gold