The Eagle's Nest#1110
"The Eagle's Nest" is an action-adventure game. The player aims to complete tasks and progress through increasingly challenging missions, developing their skills and achieving higher scores. However, succeeding in this game is not easy.
The game features a non-linear storyline, allowing the player to choose from several alternative missions. There is one rule: a player can only select missions that are harder than any mission they have already completed. Once a mission is completed, it becomes unavailable to the player. The only exceptions are the first and the final missions, which are never removed and do not appear in the list of available missions. As you might guess, these are the easiest and hardest missions, respectively. It is possible to finish the game without playing many missions. To reward those who complete the maximum number of missions, the game offers special in-game achievements and recognition.
For the most dedicated players, there are even more enticing in-game rewards. Let be the maximum number of missions that can be completed in a single playthrough. If a player manages to play the game several times (each time starting from the first mission and ending with the last), each time completing exactly missions and achieving the maximum possible under the given constraints, all missions will be fully unlocked and the player will gain special recognition.
Your task is simple: help the dedicated player determine the maximum number of missions that can be completed under the given constraints. The order of missions in each game is important and must follow the storyline.
The first line contains an integer (2 < n < 100). Each of the next lines contains the name of a mission and its difficulty level. The mission name is a string of up to characters, and the difficulty level is a positive integer. Mission names are case-sensitive and can contain only letters, digits, and underscores. The difficulty level does not exceed 10^8. No mission name is repeated in any test case.
Print the maximum number of missions that can be completed under the given constraints. This number does not include the first and the last missions.
Example 1
Example 2