A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:


	Adding scenic locations, one at a time.
	Querying the ith best location of all locations already added, where i is the number of times the system has been queried (including the current query).
	
		For example, when the system is queried for the 4th time, it returns the 4th best location of all locations already added.
	
	


Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:


	SORTracker() Initializes the tracker system.
	void add(string name, int score) Adds a scenic location with name and score to the system.
	string get() Queries and returns the ith best location, where i is the number of times this method has been invoked (including this invocation).


&nbsp;
Example 1:

Input
["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]
[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
Output
[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

Explanation
SORTracker tracker = new SORTracker(); // Initialize the tracker system.
tracker.add("bradford", 2); // Add location with name="bradford" and score=2 to the system.
tracker.add("branford", 3); // Add location with name="branford" and score=3 to the system.
tracker.get();              // The sorted locations, from best to worst, are: branford, bradford.
                            // Note that branford precedes bradford due to its higher score (3 &gt; 2).
                            // This is the 1st time get() is called, so return the best location: "branford".
tracker.add("alps", 2);     // Add location with name="alps" and score=2 to the system.
tracker.get();              // Sorted locations: branford, alps, bradford.
                            // Note that alps precedes bradford even though they have the same score (2).
                            // This is because "alps" is lexicographically smaller than "bradford".
                            // Return the 2nd best location "alps", as it is the 2nd time get() is called.
tracker.add("orland", 2);   // Add location with name="orland" and score=2 to the system.
tracker.get();              // Sorted locations: branford, alps, bradford, orland.
                            // Return "bradford", as it is the 3rd time get() is called.
tracker.add("orlando", 3);  // Add location with name="orlando" and score=3 to the system.
tracker.get();              // Sorted locations: branford, orlando, alps, bradford, orland.
                            // Return "bradford".
tracker.add("alpine", 2);   // Add location with name="alpine" and score=2 to the system.
tracker.get();              // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
                            // Return "bradford".
tracker.get();              // Sorted locations: branford, orlando, alpine, alps, bradford, orland.
                            // Return "orland".


&nbsp;
Constraints:


	name consists of lowercase English letters, and is unique among all locations.
	1 &lt;= name.length &lt;= 10
	1 &lt;= score &lt;= 105
	At any time, the number of calls to get does not exceed the number of calls to add.
	At most 4 * 104 calls in total will be made to add and get.


from heapq import *

class MinHeapItem:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    def __lt__(self, other):
        return self.score < other.score or \
               (self.score == other.score and self.name > other.name)

class MaxHeapItem:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    def __lt__(self, other):
        return self.score > other.score or \
               (self.score == other.score and self.name < other.name)

class SORTracker:
    def __init__(self):
        self.min_heap = []
        self.max_heap = []
        self.i = 1

    def add(self, name: str, score: int) -> None:
        current = MinHeapItem(name, score)
        if len(self.min_heap) < self.i:
            heappush(self.min_heap, current)
        elif current > self.min_heap[0]:
            temp = heapreplace(self.min_heap, current)
            heappush(self.max_heap, MaxHeapItem(temp.name, temp.score))
        else:
            heappush(self.max_heap, MaxHeapItem(name, score))

    def get(self) -> str:
        ans = self.min_heap[0].name
        self.i += 1
        if self.max_heap:
            temp = heappop(self.max_heap)
            heappush(self.min_heap, MinHeapItem(temp.name, temp.score))
        return ans
class SORTracker {

    private TreeMap<Integer, List<String>> map;
    private int queryNum;

    // Find suitable position for name in the list
    private int getIndex(String name, List<String> list) {
        int l = 0, r = list.size() - 1, m = 0;
        while (l < r) {
            m = l + (r - l) / 2;
            if(name.compareTo(list.get(m)) > 0) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return name.compareTo(list.get(l)) > 0 ? l+1 : l;
    }

    public SORTracker() {
        map = new TreeMap<>((a,b) -> (b-a));
        queryNum = 0;
    }

    public void add(String name, int score) {
        List<String> list = map.getOrDefault(score, new ArrayList<>());
        int index = (list.size() == 0) ? 0 : getIndex(name, list);
        list.add(index, name);
        map.put(score, list);
    }

    public String get() {
        int index = queryNum;
        for (int score: map.keySet()) {
            if (index < map.get(score).size()) {
                queryNum++;
                return map.get(score).get(index);
            }
            index -= map.get(score).size();
        }
        return "";
    }
}
struct compareMin
{
    bool operator() (pair<int,string> p1, pair<int,string> p2) {
        if(p1.first == p2.first) return p1.second < p2.second;
        return p1.first > p2.first;
    }
};

struct compareMax
{
    bool operator() (pair<int,string> p1, pair<int,string> p2) {
        if(p1.first == p2.first) return p1.second > p2.second;
        return p1.first < p2.first;
    }
};

class SORTracker {
public:
    priority_queue <pair<int,string>, vector<pair<int,string>>, compareMin> min_heap;
    priority_queue <pair<int,string>, vector<pair<int,string>>, compareMax> max_heap;

    SORTracker() {}

    void add(string name, int score) {
        if(!min_heap.empty() && (min_heap.top().first < score || (min_heap.top().first == score && min_heap.top().second > name))) {
                pair<int,string> t = min_heap.top();
                min_heap.pop();
                min_heap.push({score,name});
                max_heap.push(t);
        } else {
            max_heap.push({score,name});
        }
    }

    string get() {
        pair<int,string> s = max_heap.top();
        max_heap.pop();
        min_heap.push(s);
        return s.second;
    }
};
var SORTracker = function() {
    this.S=new AVL(),this.i=1
};
SORTracker.prototype.add = function(name, score) {
    this.S.insert([name,score])
};
SORTracker.prototype.get = function() {
    return this.S.findKthNODE(this.i++)[0]
};

// B O I  L E R P L A T E 
class AVL{
    constructor(){
        this.nodeCount=0
        this.root=null

        // MODIFY THIS EVERY TIME.
        this.NODE=class{
            constructor(val,left=null,right=null,parent=null,bf=0,height=0){
                this.val=val
                this.left=left,this.right=right,this.parent=parent
                this.bf=bf,this.height=height
                this.SubTreeNodes=1
            }
        }
    }
    
//===M O D I F Y   FOR     COMPLEX     NODES==\\
    NODIFY(val){  //should return a new node based on the stats given
        return new this.NODE(val)
    }
    comparator=(node1,node2)=>{// basic comparator that returns <0,0,>0 if node1>node2,node1==node2,node1<node2
        if(node1.val[1]===node2.val[1]){
             if(node2.val[0]>node1.val[0])
                 return -1
            return 1
        }
        return Number(node2.val[1])-Number(node1.val[1])
    }
//-------------U S A B L E------------------\\
    //returns true if the value was inserted successfully
    //returns false if the value already exists
    insert(NODE){ //O(logn) 
        if(NODE===null)
            return false
        NODE=this.NODIFY(NODE)
        if(!this.contains(this.root,NODE)){
            this.root=this.ins(this.root,NODE)
            this.nodeCount++
            return true
        }
        return false
    }
    remove(NODE){ 
        if(NODE===null)
            return false
        NODE=this.NODIFY(NODE)
       // console.log(this.contains(this.root,new Node(7)))
        if(this.contains(this.root,NODE)){
            this.root=this.rem(this.root,NODE)
            this.nodeCount--
            return true
        }
        return false
        //rebalance the tree
    }
    has(NODE){
        NODE=this.NODIFY(NODE)
        return this.contains(this.root,NODE)
    }
    traversalASC(){ //O(n)
        let result=[]
        let dfs=(node)=>{
            if(!node)
                return
            dfs(node.left)
            result.push(node)
            dfs(node.right)
        }
        dfs(this.root)
        return result
    }
    findNextSmaller(NODE){
        NODE=this.NODIFY(NODE)
        let cur=this.root,result=null
        while(cur!==null){
            if(this.comparator(cur,NODE)<0)
                result=cur,
                cur=cur.right
            else
                cur=cur.left
        }
        if(result===null)
            return false // no such element
        return result
    }
    findNextBigger(NODE){
        NODE=this.NODIFY(NODE)
        let cur=this.root,result=null
        while(cur!==null){
            if(this.comparator(cur,NODE)<=0)
                cur=cur.right
            else
                result=cur,
                cur=cur.left
        }
        if(result===null)
            return false // no such element
        return result
    }
    findKthNODE(k){ //RETURNS THE NODE, NOT THE VALUE
        if(this.nodeCount<k)
            return null
        return this.findKth(this.root,k)
    }
    min=()=>this.findMin(this.root).val
    max=()=>this.findMax(this.root).val
//--------- I N T E R N A L S -----------------\\
    contains(node,val){
        if(node===null)
            return false
        let compare=this.comparator(node,val)
        if(compare<0) //node<val
            return this.contains(node.right,val)
        if(compare>0)
            return this.contains(node.left,val)
        return true
    }
    //inserts newNode to target node
    ins(tree,value){
        if(tree===null)
            return value
        //(target is bigger? insert it to the left): else to the right
        if(this.comparator(tree,value)>0)
            tree.left=this.ins(tree.left,value)
        else
            tree.right=this.ins(tree.right,value)
        //update balance factor of the target
        this.update(tree) 
        return this.rebalance(tree) //balance the target if it needs rebalancing
    }
    rem(node,elem){
        if(node===null)
            return null
        //search an existing node with the given value
        let compare=this.comparator(elem,node)//-----
        if(compare<0)
            node.left=this.rem(node.left,elem)
        else if(compare>0)
            node.right=this.rem(node.right,elem)
        else{ //node found
             //remove the node and replace it with its sucessor
            if(node.left===null)
                return node.right
            else if(node.right===null)
                return node.left
            else{ //still has both subtrees? 
                if(node.left.height>node.right.height){
                    let successor=this.findMax(node.left)/////
                    node.val=successor.val
                    node.left=this.rem(node.left,successor)
                }   
                else{
                    let successor=this.findMin(node.right)
                    node.val=successor.val
                    node.right=this.rem(node.right,successor)
                }
            }
        }
        this.update(node)
        return this.rebalance(node)
    }
    //find the min and max node of the subtree rooted at (node)
    findMin=(node)=>node.left?this.findMin(node.left):node
    findMax=(node)=>node.right?this.findMax(node.right):node
    //balances the subtree rooted at node if it is imbalanced (has balancefactor=+-2)
    //and returns the now balanced node
    rebalance(node){  //4 cases, 4 rotations
        if(node.bf==-2){
            if(node.left.bf<=0)
                return this.LL(node)
            else
                return this.LR(node)
        }
        else if(node.bf==2){
            if(node.right.bf>=0)
                return this.RR(node)
            else
                return this.RL(node)
        }
        return node
    }
    //update the balance factor and the height of the current node
    update(node){ 
        let leftHeight=node.left!==null?node.left.height:-1,rightHeight=node.right!==null?node.right.height:-1
        node.height=Math.max(leftHeight,rightHeight)+1
        node.bf=rightHeight-leftHeight
        node.SubTreeNodes=1+(node.left===null?0:node.left.SubTreeNodes )+(node.right===null?0:node.right.SubTreeNodes)
    }

    //4 cases of unbalanced trees
    LL=(node)=>this.rightRotation(node)
    RR=(node)=>this.leftRotation(node)
    LR(node){
        node.left=this.leftRotation(node.left)
        return this.LL(node)
    }
    RL(node){
        node.right=this.rightRotation(node.right)
        return this.RR(node)
    }
    //2 total rotations that work on RR and LL cases
    leftRotation(node){
        let newParent=node.right
        node.right=newParent.left
        newParent.left=node
        this.update(node)
        this.update(newParent)
        return newParent
    }
    rightRotation(node){
        let newParent=node.left
        node.left=newParent.right
        newParent.right=node
        this.update(node)
        this.update(newParent)
        return newParent
    }
    findKth(node,k){
        let leftCount=node.left?node.left.SubTreeNodes:0
        if(leftCount+1===k)
            return node.val
        if(leftCount+1<k)
            return this.findKth(node.right,k-leftCount-1)
        
        return this.findKth(node.left,k)
    }
}
Sequentially Ordinal Rank Tracker