Cookie Selection

As the chief programmer at a cookie production plant, you must ensure that every cookie the plant produces and packages meets a very demanding quality standard.

Your production line continuously bakes new cookies and places them in a holding area, where they wait to be packaged. From time to time the packaging unit requests that one cookie be sent from the holding area to be packaged. A packaging request is never issued while the holding area is empty.

What complicates matters are surprise inspections. An inspector may demand that the next few cookies bound for packaging be handed to them instead; if those cookies look (and taste) consistent, you pass the inspection, otherwise you fail.

Fortunately, the plant can measure cookie diameters to a precision of 1 nanometre (nm). To be ready for inspections, on every packaging request you send the cookie with the median diameter among all cookies currently in the holding area. If no cookie has exactly the median diameter, you instead send the smallest cookie whose diameter is larger than the median.

Concretely, sort the cookies in the holding area by ascending diameter. If the holding area contains $c$ cookies, then on a request you send the cookie at the following position (1-indexed) in the sorted order:

• if $c$ is odd, the cookie at position $\frac{c+1}{2}$;
• if $c$ is even, the cookie at position $\frac{c}{2}+1$.

Each line of input contains one of the following:

• a positive integer $d$ — a freshly baked cookie of diameter $d$ nm has arrived in the holding area;
• the symbol # — the packaging unit requests that one cookie be sent for packaging.

There are at most 600,000 lines of input, and the holding area is empty before the first cookie arrives. The plant's oven cannot bake a cookie with a diameter larger than 30 centimetres (cm), i.e. 300,000,000 nm.

For each packaging request, output the diameter in nm of the cookie sent for packaging, one per line, in the same order the requests are processed.