def insert(self, idx, val):
<EOL>_len = self._len<EOL>_lists = self._lists<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>if not _maxes:<EOL><INDENT>_maxes.append(val)<EOL>_lists.append([val])<EOL>self._len = <NUM_LIT:1><EOL>return<EOL><DEDENT>if not idx:<EOL><INDENT>if val > _lists[<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>_lists[<NUM_LIT:0>].insert(<NUM_LIT:0>, val)<EOL>self._expand(<NUM_LIT:0>)<EOL>self._len += <NUM_LIT:1><EOL>return<EOL><DEDENT><DEDENT>if idx == _len:<EOL><INDENT>pos = len(_lists) - <NUM_LIT:1><EOL>if _lists[pos][-<NUM_LIT:1>] > val:<EOL><INDENT>msg = '<STR_LIT>'.format(val, _len)<EOL>raise ValueError(msg)<EOL><DEDENT>else:<EOL><INDENT>_lists[pos].append(val)<EOL>_maxes[pos] = _lists[pos][-<NUM_LIT:1>]<EOL>self._expand(pos)<EOL>self._len += <NUM_LIT:1><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(_lists[pos_before]) - <NUM_LIT:1><EOL><DEDENT>else:<EOL><INDENT>pos_before = pos<EOL><DEDENT>before = _lists[pos_before][idx_before]<EOL>if before <= val <= _lists[pos][idx]:<EOL><INDENT>_lists[pos].insert(idx, val)<EOL>self._expand(pos)<EOL>self._len += <NUM_LIT:1><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.