높은 카드가 이긴다 (High Card Wins)

암소 베시는 카드 게임의 엄청난 팬입니다. 소에게는 카드를 쥘 수 있는 엄지손가락이 없다는 점을 고려하면 꽤 놀라운 일이죠. 불행히도 무리 중 어떤 소도 베시의 좋은 상대가 되지 못합니다. 사실 다른 소들은 게임을 너무 못해서 항상 완벽하게 예측 가능한 방식으로만 카드를 냅니다! 그럼에도 불구하고, 베시가 이길 방법을 찾아내는 것은 여전히 까다로운 일일 수 있습니다.

베시와 그녀의 친구 엘시는 현재 1부터 2N까지 번호가 매겨진 2N장의 카드를 사용하는 간단한 카드 게임을 하고 있습니다. 카드를 베시가 N장, 엘시가 N장씩 나누어 가집니다.
그런 다음 두 소는 N번의 라운드를 진행하며, 각 라운드마다 베시와 엘시는 각각 한 장의 카드를 냅니다. 이 게임에서는 카드의 숫자가 더 높은 플레이어가 1점을 얻습니다.

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

입력

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

출력

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

힌트

입력을 통해 엘시가 1, 6, 4번 카드를 낼 것임을 알 수 있으므로, 베시의 손에는 반드시 남은 카드인 2, 3, 5번 카드가 있어야 합니다.
베시는 엘시의 4번 카드를 이기기 위해 5번 카드를 끝까지 아껴두는 등의 전략을 사용하여 최대 2점을 얻을 수 있습니다.

출처

USACO 2015 December Contest, Silver

Line 1: \(N\) (\(1 \le N \le 50000\)). Next \(N\) lines: Elsie's cards, one per line.

Print Bessie's maximum score.

riseoj 작성

출처 Online Judge > GoldOJ