class SkipListNode {
    SkipListNode[] next;
    double key;
    String value;

    SkipListNode(int maxLevel) {
	next = new SkipListNode[maxLevel];
	
    }

    SkipListNode() {
	next = new SkipListNode[32];
	
    }

    SkipListNode(SkipListNode[] aNext, double aKey, String aValue) {
	next = aNext;
	key = aKey;
	value = aValue;
    }
}

class SkipListPosition {
    SkipListNode[] positionAtLevel;
    int foundLevel;

    SkipListPosition(int levels) {
	positionAtLevel = new SkipListNode[levels];
    }
}

class SkipList {
    static SkipListPosition findPos(SkipListNode origin, double key) {
	SkipListPosition position = new SkipListPosition(origin.next.length);
	SkipListNode current = origin;
	int level = origin.next.length - 1;
	boolean foundExact = false;

	while(!foundExact && level >= 0) {
	    if (current.next[level] == null || 
		current.next[level].key > key) {
		position.positionAtLevel[level] = current;
		level--;
	    } else if (current.next[level].key == key) {
		position.positionAtLevel[level] = current.next[level];
		foundExact = true;
	    } else {
		current = current.next[level];
	    }
	}
	position.foundLevel = level;

	return position;
    }

    static SkipListPosition findPreceding(SkipListNode origin, double key) {
	SkipListPosition position = new SkipListPosition(origin.next.length);
	SkipListNode current = origin;
	int level = origin.next.length - 1;

	while(level >= 0) {
	    if (current.next[level] == null || 
		current.next[level].key >= key) {
		position.positionAtLevel[level] = current;
		level--;
	    } else {
		current = current.next[level];
	    }
	}
	position.foundLevel = -1;

	return position;
    }

    final static double PROBABILITY = 0.5;

    static int randomLevel(int maxLevel) {
	int level = 0;
	while(level < maxLevel && Math.random() < PROBABILITY) {
	    level++;
	}
	return level;
    }

    static void put(SkipListNode origin, double key, String value) {
	SkipListPosition position = findPos(origin, key);
	if (position.foundLevel >= 0) {
	    position.positionAtLevel[position.foundLevel].value = value;
	} else {
	    int level = randomLevel(origin.next.length-1);
	    SkipListNode newNode = new SkipListNode(new SkipListNode[level+1], key, value);
	    for(int i=0; i<=level; i++) {
z		newNode.next[i] = position.positionAtLevel[i].next[i];
		position.positionAtLevel[i].next[i] = newNode;
	    }
	}
    }

    static boolean isFound(SkipListNode origin, double key) {
	return findPos(origin, key).foundLevel >= 0;
    }

    static String get(SkipListNode origin, double key) {
	SkipListPosition p = findPos(origin, key);
	if (p.foundLevel >= 0) {
	    return p.positionAtLevel[p.foundLevel].value;
	} else {
	    return null;
	}
    }

    static void remove(SkipListNode origin, double key) {
	SkipListPosition p = findPreceding(origin, key);
	assert(p.foundLevel == -1);
	SkipListNode before = p.positionAtLevel[0];
	assert(before != null);
	assert(before==origin || before.key < key);
	SkipListNode current = before.next[0];
	if (current != null) {
	    assert(current.key >= key);
	    if (current.key == key) {
		for(int level=0; level<current.next.length; level++) {
		    p.positionAtLevel[level].next[level] = current.next[level];
		}
	    }
	}
    }

    static void print(SkipListNode origin) {
	for(SkipListNode node=origin.next[0];
	    node != null;
	    node = node.next[0]) {
	    System.out.println(node.key + ", " + node.value);
	}
    }

    static int length(SkipListNode origin) {
	int count=0;
	for(SkipListNode node=origin.next[0]; node!=null; node=node.next[0]) {
	    count++;
	}
	return count;
    }
}