def insert(self, idx, val):
_len = self._len<EOL>_lists = self._lists<EOL>_keys = self._keys<EOL>_maxes = self._maxes<EOL>if idx < <NUM_LIT:0>:<EOL><INDENT>idx += _len<EOL><DEDENT>if idx < <NUM_LIT:0>:<EOL><INDENT>idx = <NUM_LIT:0><EOL><DEDENT>if idx > _len:<EOL><INDENT>idx = _len<EOL><DEDENT>key = self._key(val)<EOL>if not _maxes:<EOL><INDENT>self._len = <NUM_LIT:1><EOL>_lists.append([val])<EOL>_keys.append([key])<EOL>_maxes.append(key)<EOL>return<EOL><DEDENT>if not idx:<EOL><INDENT>if key > _keys[<NUM_LIT:0>][<NUM_LIT:0>]:<EOL><INDENT>msg = '<STR_LIT>'.format(val, <NUM_LIT:0>)<EOL>raise ValueError(msg)<EOL><DEDENT>else:<EOL><INDENT>self._len += <NUM_LIT:1><EOL>_lists[<NUM_LIT:0>].insert(<NUM_LIT:0>, val)<EOL>_keys[<NUM_LIT:0>].insert(<NUM_LIT:0>, key)<EOL>self._expand(<NUM_LIT:0>)<EOL>return<EOL><DEDENT><DEDENT>if idx == _len:<EOL><INDENT>pos = len(_keys) - <NUM_LIT:1><EOL>if _keys[pos][-<NUM_LIT:1>] > key:<EOL><INDENT>msg = '<STR_LIT>'.format(val, _len)<EOL>raise ValueError(msg)<EOL><DEDENT>else:<EOL><INDENT>self._len += <NUM_LIT:1><EOL>_lists[pos].append(val)<EOL>_keys[pos].append(key)<EOL>_maxes[pos] = _keys[pos][-<NUM_LIT:1>]<EOL>self._expand(pos)<EOL>return<EOL><DEDENT><DEDENT>pos, idx = self._pos(idx)<EOL>idx_before = idx - <NUM_LIT:1><EOL>if idx_before < <NUM_LIT:0>:<EOL><INDENT>pos_before = pos - <NUM_LIT:1><EOL>idx_before = len(_keys[pos_before]) - <NUM_LIT:1><EOL><DEDENT>else:<EOL><INDENT>pos_before = pos<EOL><DEDENT>before = _keys[pos_before][idx_before]<EOL>if before <= key <= _keys[pos][idx]:<EOL><INDENT>self._len += <NUM_LIT:1><EOL>_lists[pos].insert(idx, val)<EOL>_keys[pos].insert(idx, key)<EOL>self._expand(pos)<EOL><DEDENT>else:<EOL><INDENT>msg = '<STR_LIT>'.format(val, idx)<EOL>raise ValueError(msg)<EOL><DEDENT>
Insert the element *val* into the list at *idx*. Raises a ValueError if
the *val* at *idx* would violate the sort order.