code: def insert(self, idx, val):
          
          _maxes, _lists, _len = self._maxes, self._lists, self._len
  
          if idx < 0:
              idx += _len
          if idx < 0:
              idx = 0
          if idx > _len:
              idx = _len
  
          if not _maxes:
              # The idx must be zero by the inequalities above.
              _maxes.append(val)
              _lists.append([val])
              self._len = 1
              return
  
          if not idx:
              if val > _lists[0][0]:
                  msg = '{0} not in sort order at index {1}'.format(repr(val), 0)
                  raise ValueError(msg)
              else:
                  _lists[0].insert(0, val)
                  self._expand(0)
                  self._len += 1
                  return
  
          if idx == _len:
              pos = len(_lists) - 1
              if _lists[pos][-1] > val:
                  msg = '{0} not in sort order at index {1}'.format(repr(val), _len)
                  raise ValueError(msg)
              else:
                  _lists[pos].append(val)
                  _maxes[pos] = _lists[pos][-1]
                  self._expand(pos)
                  self._len += 1
                  return
  
          pos, idx = self._pos(idx)
          idx_before = idx - 1
          if idx_before < 0:
              pos_before = pos - 1
              idx_before = len(_lists[pos_before]) - 1
          else:
              pos_before = pos
  
          before = _lists[pos_before][idx_before]
          if before <= val <= _lists[pos][idx]:
              _lists[pos].insert(idx, val)
              self._expand(pos)
              self._len += 1
          else:
              msg = '{0} not in sort order at index {1}'.format(repr(val), idx)
              raise ValueError(msg)
docs: Insert the element *val* into the list at *idx*. Raises a ValueError if
          the *val* at *idx* would violate the sort order.