Stack With Frequency

easy

1. Given a custom data structure named "FreqStack".
  2. FreqStack has two functions:
  	  * push(int x), which pushes an integer x onto the stack.
  	  * pop(), which removes and returns the most frequent element in the stack.
  3. If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.     
  4. Function signatures are given, you just need to complete these functions.
  5.  Your FreqStack object will be instantiated and then the inputs will be:
   	  * For push(val) --> 1 val;
  	    Example push(1) --> 1 1
   	  * For pop() --> 2;

Input Format

First line contains 'N' number of integers to be entered. Second line contains N integers( For push(val) write 1 val, for pop() write 2)

Output Format

First line contains the values returned by pop() function.

Constraints

For push(int x) will be such that 0 <= x <= 10^9.
  It is guaranteed that pop() won't be called if the stack has zero elements.

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

16
1 5 1 7 1 5 1 7 1 4 1 5 2 2 2 2

Output

Queue Using Linkedlist

Tiny Big Tyny