class RangeSearchBST extends RedBlackBSTWithNoExtraMemory<Key, Val> {

    public int size(Key lo, Key hi) {
        if (lo == null || hi == null || lo.compareTo(hi) > 0)
            throw new IllegalArgumentException("input is not valid");
        if (contains(hi)) return rank(hi) - rank(lo) + 1;
        return rank(hi) - rank(lo);
    }

}