public class Container < Key extends java.lang.Comparable < Key > , Value > { 
    private Node root; 
    private class Node { 
        private Key key; 
        private Value val; 
        private Node left, right; 
        private int N; 
        public Node(Key key, Value val, int N) { 
            this.key = key; 
            this.val = val; 
            this.N = N; 
        } 
    } 
    public int size() { 
        return size(root); 
    } 
    private int size(Node x) { 
        if (x == null) 
            return 0; 
        else 
            return x.N; 
    } 
    public Value get(Key key) { 
        return get(root, key); 
    } 
    private Value get(Node x, Key key) { 
        if (x == null) 
            return null; 
        int cmp = key.compareTo(x.key); 
        if (cmp < 0) 
            return get(x.left, key); 
        else 
        if (cmp > 0) 
            return get(x.right, key); 
        else 
            return x.val; 
    } 
    public void put(Key key, Value val) { 
        root = put(root, key, val); 
    } 
    private Node put(Node x, Key key, Value val) { 
        if (x == null) 
            return new Node(key, val, 1); 
        int cmp = key.compareTo(x.key); 
        if (cmp < 0) 
            x.left = put(x.left, key, val); 
        else 
        if (cmp > 0) 
            x.right = put(x.right, key, val); 
        else 
            x.val = val; 
        x.N = size(x.left) + size(x.right) + 1; 
        return x; 
    } 
}

public class Container < Key extends java.lang.Comparable < Key > , Value > { 
    private Node root; 
    private class Node { 
        Key key; 
        Value val; 
        Node left, right; 
        I nt N; 
        boolean param; 
        Node(Key key, Value val, int N, boolean param) { 
            this.key = key; 
            this.val = val; 
            this.N = N; 
            this.param = param; 
        } 
    } 
    private boolean check(Node x) { 
        if (x == null) 
            return false; 
        return x.param == true; 
    } 
    Node rotateLeft(Node h) { 
        Node x = h.right; 
        h.right = x.left; 
        x.left = h; 
        x.param = h.param; 
        h.param = true; 
        x.N = h.N; 
        h.N = 1 + size(h.left) + size(h.right); 
        return x; 
    } 
    Node rotateRight(Node h) { 
        Node x = h.left; 
        h.left = x.right; 
        x.right = h; 
        x.param = h.param; 
        h.param = true; 
        x.N = h.N; 
        h.N = 1 + size(h.left) + size(h.right); 
        return x; 
    } 
    void flip(Node h) { 
        h.param = true; 
        h.left.param = false; 
        h.right.param = false; 
    } 
    private int size(Node x) { 
        if (x == null) 
            return 0; 
        else 
            return x.N; 
    } 
    public void put(Key key, Value val) { 
        root = put(root, key, val); 
        root.param = false; 
    } 
    private Node put(Node h, Key key, Value val) { 
        if (h == null) 
            return new Node(key, val, 1, true); 
        int cmp = key.compareTo(h.key); 
        if (cmp < 0) 
            h.left = put(h.left, key, val); 
        else 
        if (cmp > 0) 
            h.right = put(h.right, key, val); 
        else 
            h.val = val; 
        if (check(h.right) && !check(h.left)) 
            h = rotateLeft(h); 
        if (check(h.left) && check(h.left.left)) 
            h = rotateRight(h); 
        if (check(h.left) && check(h.right)) 
            flip(h); 
        h.N = size(h.left) + size(h.right) + 1; 
        return h; 
    } 
}

public class Container < Key extends java.lang.Comparable < Key > , Value > { 
    private Key[] keys; 
    private Value[] vals; 
    private int N; 
    public Container(int capacity) { 
        keys = (Key[]) new java.lang.Comparable[capacity]; 
        vals = (Value[]) new Object[capacity]; 
    } 
    public int size() { 
        return N; 
    } 
    public Value get(Key key) { 
        if (vals.length == 0) 
            return null; 
        int i = rank(key); 
        if (i < N && keys[i].compareTo(key) == 0) 
            return vals[i]; 
        else 
            return null; 
    } 
    private int rank(Key key) { 
        int lo = 0, hi = N - 1; 
        while (lo <= hi) { 
            int mid = lo + (hi - lo) / 2; 
            int cmp = key.compareTo(keys[mid]); 
            if (cmp < 0) 
                hi = mid - 1; 
            else 
            if (cmp > 0) 
                lo = mid + 1; 
            else 
                return mid; 
        } 
        return lo; 
    } 
    public void put(Key key, Value val) { 
        int i = rank(key); 
        if (i < N && keys[i].compareTo(key) == 0) { 
            vals[i] = val; 
            return; 
        } 
        for (int j = N; j > i; j--) { 
            keys[j] = keys[j - 1]; 
            vals[j] = vals[j - 1]; 
        } 
        keys[i] = key; 
        vals[i] = val; 
        N++; 
    } 
}