[백준] 7662번이중 우선순위 큐 (gold 4

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        PriorityQueue<Integer> aque=new PriorityQueue<>();
        PriorityQueue<Integer> rque=new PriorityQueue<>(Collections.reverseOrder());
        HashMap<Integer,Integer> dict=new HashMap<>();

        int t=Integer.valueOf(br.readLine());
        for(int cs=0; cs<t; cs++){
            aque.clear();
            rque.clear();
            dict.clear();

            int n=Integer.valueOf(br.readLine());
            for(int i=0; i<n; i++) {
                st = new StringTokenizer(br.readLine());

                char c = st.nextToken().charAt(0);
                int mid = Integer.valueOf(st.nextToken());

                if (c == 'I') {
                    aque.offer(mid);
                    rque.offer(mid);
                    if (dict.get(mid) == null) {
                        dict.put(mid, 1);
                    }
                    else {
                        dict.replace(mid, dict.get(mid) + 1);
                    }
                }
                else {
                    if (mid == 1) {
                        while(!rque.isEmpty()){
                            int temp=rque.poll();
                            if(dict.get(temp)==0){
                                continue;
                            }
                            dict.replace(temp, dict.get(temp)-1);
                            break;
                        }
                    }
                    else{
                        while(!aque.isEmpty()){
                            int temp=aque.poll();
                            if(dict.get(temp)==0){
                                continue;
                            }
                            dict.replace(temp, dict.get(temp)-1);
                            break;
                        }
                    }
                }
            }

            int mn=Integer.MAX_VALUE;
            int mx=Integer.MIN_VALUE;
            boolean find=false;
            while(!rque.isEmpty()){
                int temp=rque.poll();
                if(dict.get(temp)!=0){
                    mx=temp;
                    find=true;
                    break;
                }
            }
            while(!aque.isEmpty()){
                int temp=aque.poll();
                if(dict.get(temp)!=0){
                    mn=temp;
                    break;
                }
            }

            bw.write(find ? mx+" "+mn+"\n" : "EMPTY\n");
        }
        bw.flush();
    }
}