import java.util.*;
class Foo{
    Map<Integer,Integer> map1;
    Map<Integer,Set<Integer>> map2;
    int max_freq;
    Foo(){
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        map2.put(0,new HashSet<>());
        max_freq = 0;
    }
    
    
    public void add(int x){
        map1.putIfAbsent(x,0);
        int curr_f = map1.get(x);
        if(!map2.containsKey(curr_f)){
            map1.put(x,1);
        }else{
            map1.merge(x,1,Integer::sum);
        }
        
        map2.putIfAbsent(map1.get(x),new HashSet<>());
        map2.get(map1.get(x)-1).remove(x); // remove from previous frequency list
        map2.get(map1.get(x)).add(x);// add to current frequency list
        max_freq = Math.max(max_freq,map1.get(x));
        printState();
    }
    
    public List<Integer> delete(){
        List<Integer> ls = new ArrayList<>(map2.get(max_freq));
        map2.remove(max_freq);
        max_freq--;
        while(max_freq > 0 && map2.get(max_freq).size() == 0) max_freq--;
        printState();
        return ls;
    }
    
    public void printState(){
        System.out.println(map1.toString());
        System.out.println("Maximum frequency: " + max_freq);
        for(Map.Entry<Integer,Set<Integer>> m : map2.entrySet()){
            System.out.println(m.getKey() + " " + m.getValue().toString());
        }
        System.out.println("----------------------------------------------------");
    }
    
}
class Ideone{
	public static void main(String[] args) {
		Foo f = new Foo();
		f.add(1);
		f.add(2);
		f.add(2);
		f.add(2);
		f.delete();
		f.delete();
	}
}