def add(self, val):
        """Add the element *val* to the list."""
        _lists = self._lists
        _keys = self._keys
        _maxes = self._maxes

        key = self._key(val)

        if _maxes:
            pos = bisect_right(_maxes, key)

            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(val)
                _keys[pos].append(key)
                _maxes[pos] = key
            else:
                idx = bisect_right(_keys[pos], key)
                _lists[pos].insert(idx, val)
                _keys[pos].insert(idx, key)

            self._expand(pos)
        else:
            _lists.append([val])
            _keys.append([key])
            _maxes.append(key)

        self._len += 1
Add the element *val* to the list.