Max Frequency Stack

easy

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

FreqStack() constructs 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

["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output Format

[null, null, null, null, null, null, null, 5, 7, 5, 4]

Constraints

0 &lt;= val &lt;= 109
At most 2 * 104 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.

Notice

Example

Input

Output

Grid Illuminate

Encode And Decode Tinyurl

Related Questions

easy Double Pair Array easy Subdomain Visit Count easy Group Anagrams easy Isomorphic Strings easy Valid Anagram easy Longest Subarray With Sum Divisible By K easy The Skyline Problem easy Word Pattern easy Number Of Employees Under Every Manager easy Find Itinerary From Tickets easy Check If An Array Can Be Divided Into Pairs Whose Sum Is Divisible By K easy Largest Subarray With Zero Sum easy Count Distinct Elements In Every Window Of Size K easy Largest Subarray With Contiguous Elements medium Count Of All Subarrays With Zero Sum hard Smallest Substring Of A String Containing All Characters Of Another String