// Arup Guha
// 4/12/2015
// Solution to NCPC Problem C: Cookie Selection

import java.util.*;
import java.io.*;

public class cookieselection {

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

		TreeSet<pair> small = new TreeSet<pair>();
		TreeSet<pair> large = new TreeSet<pair>();
		int index = 0;

		// Go through all input.
		while (stdin.ready()) {

			String s = stdin.readLine().trim();

			// Remove.
			if (s.charAt(0) == '#') {

				int retval = large.pollFirst().value;
				System.out.println(retval);

				// Keep balance.
				if (small.size() > large.size())
					large.add(small.pollLast());

			}

			// Add
			else {

				// Get value to add.
				int value = Integer.parseInt(s);

				// Smaller than median, put there.
				if (small.size() > 0 && value < small.last().value) {
					small.add(new pair(value, index));
					if (small.size() > large.size())
						large.add(small.pollLast());
				}

				// Larger than median...
				else {
					large.add(new pair(value, index));
					if (large.size() > small.size()+1)
						small.add(large.pollFirst());
				}

				// For next add...
				index++;
			}
		}
	}
}

class pair implements Comparable<pair> {

	public int value;
	public int index;

	public pair(int v, int i) {
		value = v;
		index = i;
	}

	public int compareTo(pair other) {
		if (this.value != other.value)
			return this.value-other.value;
		return this.index - other.index;
	}
}