void main(){
    SkipList skipList = new SkipList();
    for(int i = 0; i < 10; i++){
        IO.println("Max nivo: "+skipList.maxNivo+", Inserted: "+i);
        skipList.vstavi(i);
        skipList.najdi(i);
        
    }
    for(long max = 512; max <= 10000000;max = max*2){
        skipList = new SkipList();
        for(int i = 0; i < max; i++){
            skipList.vstavi(i);
        }
        int sum = 0;
        for(int i = 0; i < 10; i++){
            long x = (long)(Math.random()*max);
            int found = skipList.najdi(x);
            sum += found;
        }
        IO.println("Size: "+max+",Max: "+skipList.maxNivo+", Time: "+sum/10);
        sum = 0;
        for(int i = 0; i < 10; i++){
            int found = skipList.najdi(Long.MAX_VALUE);
            sum += found;
        }
        IO.println("Size: "+max+ ", Time: "+sum/10);

    }
}  


public class SkipList{
    public static final int MAX_LEVEL = 16;
    public int maxNivo=1;
    SkipListNode[] glava = new SkipListNode[MAX_LEVEL];

    public SkipList(){
        var start = new SkipListNode(Long.MIN_VALUE);
        for (int i = 0; i < MAX_LEVEL; i++) {
            glava[i] = start;
        }
    }
    
    public int najdi(long vrednost){
        SkipListNode trenutni = null;
        int nivo=-1;
        int count =0;
        for(int i = maxNivo-1; i >= 0; i--){
            count++;
            if(glava[i].vrednost == vrednost){ return count;}
            else if(glava[i].vrednost < vrednost){
                trenutni = glava[i];
                nivo =i;
                break;
            }
        }
        while(trenutni != null){
            count++;
            if(trenutni.vrednost == vrednost){ return count;}
            if(trenutni.repi[nivo] != null && trenutni.repi[nivo].vrednost <= vrednost){
                trenutni = trenutni.repi[nivo];
            }
            else{
                nivo--;
            }
            if(nivo < 0){ break;}
        }
        return count;
    }
    public boolean vstavi(int vrednost){
        SkipListNode trenutni = null;
        SkipListNode novi = new SkipListNode(vrednost);
        int noviMax=novi.repi.length;        
        int nivo=-1;
        for(int i = maxNivo-1; i >= 0; i--){
            if(glava[i].vrednost == vrednost){ return false;}
            else if(glava[i].vrednost < vrednost){
                trenutni = glava[i];
                nivo =i;
                break;
            }
        }
        if(noviMax > maxNivo){
            for(int i = maxNivo; i < noviMax; i++){
                glava[i] = novi;
            }
            maxNivo = noviMax;
        }
        while(trenutni != null){
            if(trenutni.vrednost == vrednost){ return false;}
            if(trenutni.repi[nivo] != null && trenutni.repi[nivo].vrednost < vrednost){
                trenutni = trenutni.repi[nivo];
            }
            else{
                if(nivo < noviMax){
                    var temp = trenutni.repi[nivo];
                    trenutni.repi[nivo] = novi;
                    trenutni.repi[nivo].repi[nivo] = temp;
                }
                nivo--;
            }
            if(nivo < 0){ break;}
        }
        return true;
    }
    void izpisi(){
        for(int i = maxNivo-1; i >= 0; i--){
            SkipListNode trenutni = glava[i];
            while(trenutni != null){
                IO.print(trenutni.vrednost+" ");
                trenutni = trenutni.repi[i];
            }
            IO.println();
        }
    }
}

public class SkipListNode {
    SkipListNode[] repi;
    long vrednost;
    public SkipListNode(long vrednost){
       
        this.vrednost = vrednost;
        int niviji = 1;
        while (Math.random() < 0.5 && niviji < SkipList.MAX_LEVEL) {
            niviji++;
        }
        this.repi = new SkipListNode[niviji];
    }
}