e-olymp
Competitions

Data structures contest - high level

Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack. The possible commands are:

  • push n - pushes an integer n onto the top of the stack;
  • pop - removes and prints the most frequent element in the stack. If there is a tie for the most frequent element, the element closest to the stack's top is removed and printed.

Input

Each line contains a single command.

Output

For each pop command print on a separate line the corresponding result.

Time limit 1 second
Memory limit 128 MiB
Input example #1
push 4
push 5
push 4
push 6
push 7
pop
push 5
pop
pop
Output example #1
4
5
7
Input example #2
push 5
push 3
push 1
push 3
push 9
pop
pop
pop
pop
pop
Output example #2
3
9
1
3
5