High Card Low Card (Gold)#11160
Bessie and her friend Elsie are currently playing a simple card game. They take a deck of cards, conveniently numbered through , and divide them equally, with each player receiving cards. They then play rounds, with each player playing one card in each round.
In the first rounds, the player who plays the higher card earns a point. In the remaining rounds, the rules are reversed, and the player who plays the lower card earns a point.
Given that Bessie can predict the order in which Elsie will play her cards, determine the maximum number of points Bessie can score.
The first line contains an integer n~(2 \le n \le 50000), where is guaranteed to be even.
The next lines contain the cards that Elsie will play in each successive round. Note that Bessie's cards can be determined from this information.
Print one integer — the maximum number of points Bessie can score.
In this example, Bessie has cards , and in her hand. She can use these cards to win at most points by saving her card for one of the rounds in the second half of the game.
Example 1