P6179 [USACO15DEC] High Card Wins S

Bessie is a loyal fan of card games. To her, the other cows are not real opponents. Worse, the other cows’ behavior while playing cards is completely predictable. Even so, Bessie knows that winning is still a challenge. Bessie and her friend Elsie are playing a card game. The game uses a deck of $2N$ cards numbered from $1$ to $2N$. Bessie and Elsie each receive $N$ cards. Then they play $N$ rounds. In each round, Bessie and Elsie each play one card. Whoever plays the card with the larger number wins that round. Bessie has already predicted Elsie’s playing order. Please help Bessie calculate the maximum number of rounds she can win.

The first line contains an integer $N$ ($1 \leq N \leq 5 \times 10^4$). The next $N$ lines each contain one integer. The $i$-th line gives the card Elsie plays in round $i$. Note that Bessie’s $N$ cards can be easily determined from the input.

Output the maximum number of rounds Bessie can win.

Bessie holds the three cards $2,3,5$. She plays $2$ in the first round, $3$ in the second round, and $5$ in the third round, thus winning rounds $1$ and $3$. It can be proven that there is no better strategy. Translated by ChatGPT 5