Squirrel and bamboo#1871
Squirrel decided to circumnavigate the globe. Upon reaching the tropics, she found that acorns became harder to find. However, she discovered a good stalk of bamboo, and now, instead of carrying acorns from one hollow tree to another each day, she carries them with her in the bamboo.
Bamboo is a tube with one end closed, and acorns can be put in or taken out only from the other end. The diameter of the tube is small, so if you put acorns in it in a certain order, you can only remove them in the reverse order.
When the squirrel finds an acorn, she immediately puts it in the bamboo. From time to time, hunger makes her take out an acorn from the bamboo and eat it; because of the construction of the bamboo, this will be the most recently found acorn remaining.
Squirrel loves to hoard acorns in the bamboo. Therefore, each time she has to take an acorn out, she feels sad. However, we know how to cheer her up! For squirrels, acorns are characterized by a quality—an integer from to 10^6. When the squirrel takes out another acorn, she would like to know the maximum quality of all acorns that still remain in the bamboo. Your task is to provide her with this information.
The first line contains the number of events n~(1 \le n \le 10^5). Each of the next lines contains a number describing the event. If the number is positive, it means the squirrel found an acorn and put it in the bamboo. If the number is zero, it means the squirrel was hungry and took an acorn from the bamboo. All numbers are integers and do not exceed 10^6. It is guaranteed that after the first query, the bamboo is never empty.
For each time an acorn is taken from the bamboo, output a single integer — the maximum quality among all acorns remaining at that moment in the bamboo.
Example 1