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();
	}
}
 

aW1wb3J0IGphdmEudXRpbC4qOwpjbGFzcyBGb297CiAgICBNYXA8SW50ZWdlcixJbnRlZ2VyPiBtYXAxOwogICAgTWFwPEludGVnZXIsU2V0PEludGVnZXI+PiBtYXAyOwogICAgaW50IG1heF9mcmVxOwogICAgRm9vKCl7CiAgICAgICAgbWFwMSA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBtYXAyID0gbmV3IEhhc2hNYXA8PigpOwogICAgICAgIG1hcDIucHV0KDAsbmV3IEhhc2hTZXQ8PigpKTsKICAgICAgICBtYXhfZnJlcSA9IDA7CiAgICB9CiAgICAKICAgIAogICAgcHVibGljIHZvaWQgYWRkKGludCB4KXsKICAgICAgICBtYXAxLnB1dElmQWJzZW50KHgsMCk7CiAgICAgICAgaW50IGN1cnJfZiA9IG1hcDEuZ2V0KHgpOwogICAgICAgIGlmKCFtYXAyLmNvbnRhaW5zS2V5KGN1cnJfZikpewogICAgICAgICAgICBtYXAxLnB1dCh4LDEpOwogICAgICAgIH1lbHNlewogICAgICAgICAgICBtYXAxLm1lcmdlKHgsMSxJbnRlZ2VyOjpzdW0pOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBtYXAyLnB1dElmQWJzZW50KG1hcDEuZ2V0KHgpLG5ldyBIYXNoU2V0PD4oKSk7CiAgICAgICAgbWFwMi5nZXQobWFwMS5nZXQoeCktMSkucmVtb3ZlKHgpOyAvLyByZW1vdmUgZnJvbSBwcmV2aW91cyBmcmVxdWVuY3kgbGlzdAogICAgICAgIG1hcDIuZ2V0KG1hcDEuZ2V0KHgpKS5hZGQoeCk7Ly8gYWRkIHRvIGN1cnJlbnQgZnJlcXVlbmN5IGxpc3QKICAgICAgICBtYXhfZnJlcSA9IE1hdGgubWF4KG1heF9mcmVxLG1hcDEuZ2V0KHgpKTsKICAgICAgICBwcmludFN0YXRlKCk7CiAgICB9CiAgICAKICAgIHB1YmxpYyBMaXN0PEludGVnZXI+IGRlbGV0ZSgpewogICAgICAgIExpc3Q8SW50ZWdlcj4gbHMgPSBuZXcgQXJyYXlMaXN0PD4obWFwMi5nZXQobWF4X2ZyZXEpKTsKICAgICAgICBtYXAyLnJlbW92ZShtYXhfZnJlcSk7CiAgICAgICAgbWF4X2ZyZXEtLTsKICAgICAgICB3aGlsZShtYXhfZnJlcSA+IDAgJiYgbWFwMi5nZXQobWF4X2ZyZXEpLnNpemUoKSA9PSAwKSBtYXhfZnJlcS0tOwogICAgICAgIHByaW50U3RhdGUoKTsKICAgICAgICByZXR1cm4gbHM7CiAgICB9CiAgICAKICAgIHB1YmxpYyB2b2lkIHByaW50U3RhdGUoKXsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4obWFwMS50b1N0cmluZygpKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk1heGltdW0gZnJlcXVlbmN5OiAiICsgbWF4X2ZyZXEpOwogICAgICAgIGZvcihNYXAuRW50cnk8SW50ZWdlcixTZXQ8SW50ZWdlcj4+IG0gOiBtYXAyLmVudHJ5U2V0KCkpewogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4obS5nZXRLZXkoKSArICIgIiArIG0uZ2V0VmFsdWUoKS50b1N0cmluZygpKTsKICAgICAgICB9CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIik7CiAgICB9CiAgICAKfQpjbGFzcyBJZGVvbmV7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CgkJRm9vIGYgPSBuZXcgRm9vKCk7CgkJZi5hZGQoMSk7CgkJZi5hZGQoMik7CgkJZi5hZGQoMik7CgkJZi5hZGQoMik7CgkJZi5kZWxldGUoKTsKCQlmLmRlbGV0ZSgpOwoJfQp9Cg==