Filling the bag P98123


Statement
 

pdf   zip

thehtml

Ali Baba is hidden in the cave of the treasure, watching how the forty thieves leave jewels and take away jewels all the time. When the thieves depart, Ali Baba will fill his bag with the most valuable jewels, but he will have to make it quickly, so that the thieves cannot catch him. Therefore, at every moment he wants to know which are the jewels that he will have to take if he has the chance. Help him!

Input

Input begins with the number of jewels that fit in the bag (a number between 1 and 105). Follow the actions of the thieves: If they leave a jewel, there is the word “leave” followed by the value of the jewel. If they take a jewel, there is the word “take” followed by the value of the jewel. The values are natural numbers, all different.

Output

For every action of the thieves, print the maximum value of the jewels that Ali Baba could take if the thieves left at that moment.

Public test cases
  • Input

    3
    leave 1000
    leave 100
    leave 400
    leave 2000
    take 1000
    leave 50
    leave 3000
    take 100
    take 2000
    leave 1500
    take 400
    take 1500
    

    Output

    1000
    1100
    1500
    3400
    2500
    2500
    5400
    5400
    3450
    4900
    4550
    3050
    
  • Input

    5
    leave 1000000000
    leave 1000000001
    leave 1000000002
    leave 1000000003
    leave 1000000004
    leave 1000000005
    

    Output

    1000000000
    2000000001
    3000000003
    4000000006
    5000000010
    5000000015
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python