import java.util.*;

public class SkipList<K extends Comparable<K>,V> extends AbstractMap<K,V> {
    private int m, size;
    private Elem l;
    private ArrayList<Elem> p;

    private class Elem implements Entry<K, V> {
        K key;
        V value;
        ArrayList<Elem> next;

        public Elem(K k, V v) {
            key = k;
            value = v;
            next = new ArrayList<Elem>();
        }
        public V setValue(V v) {
            this.value = v;
            return value;
        }
        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }
    }

    public SkipList(int levels) { //InitSkipList(in m, out l)
        size = 0;
        m = levels;
        l = new Elem(null, null);
        int i=0;
        while(i<m) {
            (l.next).add(i,null);
            i++;
        }
        this.p = new ArrayList<Elem>();
    }
    public Elem MapEmpty(Elem l)//Map_Empty
    {
        l.next.set(0,null);
        return l.next.get(0);
    }

    public Elem succ(Elem x) //succ
    {
        return x.next.get(0);
    }

    public ArrayList<Elem> skip(K key){ //skip
        int i=0, j=0;
        Elem x=l;
        i=m-1;
        while(i>=0){
            while(x.next.get(i)!=null && x.next.get(i).key.compareTo(key) < 0)
            {
                x=x.next.get(i);
            }
            p.add(j++,x);
            i--;
        }
        return p;
    }

    public V put(K key, V value){ //insert
        int i=0;
        p=skip(key);
        if (p.get(0).next.get(0) != null && p.get(0).next.get(0).key.equals(key)) {
            V panic = p.get(0).next.get(0).value;
            p.get(0).next.get(0).setValue(value);
            return panic;
        }
        Elem x=new Elem(key,value);
        while(i<m){
            (x.next).add(null);
            i++;
        }
        int r=((int)Math.random()*1000000)*2;
        i=0;
        while (i<m && r%2==0){
            x.next.set(i,p.get(i).next.get(i));
            p.get(i).next.set(i, x);
            i++;
            r=r/2;
        }
        while(i<m){
            x.next.set(i, null);
            i++;
        }
        size++;
        return null;
    }

    public V get(K key) {//lookup
        p=skip(key);
        Elem x=succ(p.get(0));
        if(x != null && x.key.equals(key)){
            return x.value;
        }
        else{
            return null;
        }
    }
    
    public V remove(K key) {//delete
        p = skip(key);
        Elem x=succ(p.get(0));
        if(x==null || x.key!=key)
            return null;
        else{
            int i=0;
            while(i<m && p.get(i).next.get(i).equals(x))
            {
                p.get(i).next.set(i,x.next.get(i));
                i++;
            }
            size--;
            return x.value;
        }
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return new MyEntrySet();
    }

    private class MyEntrySet extends AbstractSet{
        public Iterator<SkipList<K, V>> iterator(){
            return new Iterator1();
        }

        private class Iterator1 implements Iterator{
            private Elem i = l;
            @Override
            public boolean hasNext() {
                return i.next.get(0) != null;
            }

            @Override
            public Elem next() {
                i = i.next.get(0);
                return i;
            }

            @Override
            public void remove(){
                SkipList.this.remove(i.getKey());
            }
        }

        @Override
        public int size() {
            return size;
        }
    }

}