High Card Wins#11158
Bessie the cow is a huge fan of card games, which is quite surprising given her lack of opposable thumbs. Unfortunately, none of the other cows in the herd are good opponents. In fact, they are so bad that they always play in a completely predictable fashion! Nonetheless, it can still be a challenge for Bessie to figure out how to win.
Bessie and her friend Elsie are currently playing a simple card game. They take a deck of cards, conveniently numbered from to , and divide them into cards for Bessie and cards for Elsie. They then play rounds. In each round, Bessie and Elsie each play a single card, and the player with the higher-valued 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~(1 \le n \le 50000).
The next lines contain the cards that Elsie will play in each successive round of the game. 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 must have cards , , and in her hand. She can use these cards to win at most points by saving the until the end to beat Elsie's .
Example 1