812. Maximum Frequency Stack

0

Medium

Create a data structure that functions like a stack, allowing elements to be pushed onto the stack and the most frequently occurring element to be popped from the stack.
Implement the FreqStack class:

- FreqStack() initializes an empty frequency stack.
- void push(int val) pushes an integer val onto the top of the stack.
- int pop() removes and returns 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 returned.

Input Format

An integer n denoting the number of operations to be performed on the implemented stack.

The Nth line contains a string and an integer denoting the operation to be performed and the integer on which the operation is to be performed. The latter value is -1 for constructor call operation and pop operations.

The Nth line contains a string and an integer denoting the operation to be performed and the integer on which the operation is to be performed. The latter value is -1 for constructor call operation and pop operations.

Output Format

A list of the returned values for each operation

Example

Input

11
FreqStack -1
push 5
push 7
push 5
push 7
push 4
push 5
pop -1
pop -1
pop -1
pop -1

Output

null null null null null null null 5 7 5 4

Constraints

0 <= val <= 10^9

At most 2 * 10^4 calls will be made to push and pop.

It is guaranteed that there will be at least one element in the stack before calling pop.

At most 2 * 10^4 calls will be made to push and pop.

It is guaranteed that there will be at least one element in the stack before calling pop.

Loading...

View Submissions

Console