Competitions

# Squirrel and bamboo

Squirrel decided to go to circumnavigate the globe. Once in the tropics, it is found that a corns become harder to find. But she found a great stalk of bamboo, and now instead of everyday to carry acorns, one from one hollow to another, carries them with him to the bamboo.

Bamboo is a tube, one end is closed and the other end can be put or remove the acorns. Tube diameter is small enough, so if you put into it acorns in a particular order, removing them only in reverse.

When a squirrel finds an acorn, it immediately puts it in bamboo. In addition, from time to time, hunger makes a squirrel to get an acorn from the bamboo and eat it, because bamboo is a device would be that of the acorn nit that the squirrel found after all.

Squirrel loves to hoard acorns in the bamboo. Therefore, each time when it comes to taking out a bamboo once an acorn, she feels sad. However, we know how to comfort her! Acorns for the squirrels are characterized by quality-an integer from 1 to 106. When the squirrel got another acorn, it would be nice to know what the maximum quality for all the acorns, which are bamboo still remain. Your task is to provide its such information.

#### Input

The first line contains number of events n (1n100000). Each of the following n rows contain the number that describes the event. If the number is positive, it means that the squirrel found an acorn and put it in your bamboo. If the number is zero, then it means that the squirrel was hungry and took an acorn from bamboo. All numbers are integers and not exceed 106. It is guaranteed that after the first query bamboo never empty.

#### Output

For each taking out a bamboo acorn output a string containing a single integer — maximum quality for all of acorns remaining at this point in the bamboo.

Time limit 1 second
Memory limit 256 MiB
Input example #1
8
3
2
4
0
4
3
0
0

Output example #1
3
4
3

Author Sergey Kopeliovich
Source Winter School, Kharkov, 2011, Day 5