High Card Low Card (Platinum)#11164
Bessie and her friend Elsie are currently playing a simple card game. They take a deck of cards, conveniently numbered through , and divide them evenly, with each player receiving cards. They then play rounds, with Bessie and Elsie each playing one card in every round.
Initially, the player who plays the higher card wins a point. However, at any point during the game, Bessie can decide to switch the rules so that, for the remainder of the game, the player who plays the lower card wins a point. Bessie can choose not to use this option, leaving the entire game in "high card wins" mode, or she can invoke it immediately, causing the entire game to follow the "low card wins" rule.
Given that Bessie knows the order in which Elsie will play her cards, determine the maximum number of points Bessie can win.
The first line contains an integer n~(2 \le n \le 50000).
The next lines contain the cards that Elsie will play in each of the successive rounds of the game. Note that Bessie's cards can be determined from this information.
Print the maximum number of points Bessie can score.
In this example, Bessie has cards , and in her hand, and she can win at most points. For example, Bessie can keep the "high card wins" rule for the entire game. She can defeat the card with her , lose to the with her , and then defeat the and with her and , respectively, for a total of 3 points.
Example 1