from __future__ import print_function import sys import traceback from bisect import bisect_left, bisect_right, insort from itertools import chain, repeat, starmap from math import log from operator import add, eq, ne, gt, ge, lt, le, iadd from textwrap import dedent try: from collections.abc import Sequence, MutableSequence except ImportError: from collections import Sequence, MutableSequence from functools import wraps from sys import hexversion if hexversion < 0x03000000: from itertools import imap as map # pylint: disable=redefined-builtin from itertools import izip as zip # pylint: disable=redefined-builtin try: from thread import get_ident except ImportError: from dummy_thread import get_ident else: from functools import reduce try: from _thread import get_ident except ImportError: from _dummy_thread import get_ident def recursive_repr(fillvalue='...'): def decorating_function(user_function): repr_running = set() @wraps(user_function) def wrapper(self): key = id(self), get_ident() if key in repr_running: return fillvalue repr_running.add(key) try: result = user_function(self) finally: repr_running.discard(key) return result return wrapper return decorating_function class SortedList(MutableSequence): DEFAULT_LOAD_FACTOR = 1000 def __init__(self, iterable=None, key=None): assert key is None self._len = 0 self._load = self.DEFAULT_LOAD_FACTOR self._lists = [] self._maxes = [] self._index = [] self._offset = 0 if iterable is not None: self._update(iterable) def __new__(cls, iterable=None, key=None): if key is None: return object.__new__(cls) else: if cls is SortedList: return object.__new__(SortedKeyList) else: raise TypeError('inherit SortedKeyList for key argument') @property def key(self): # pylint: disable=useless-return return None def _reset(self, load): values = reduce(iadd, self._lists, []) self._clear() self._load = load self._update(values) def clear(self): self._len = 0 del self._lists[:] del self._maxes[:] del self._index[:] self._offset = 0 _clear = clear def add(self, value): _lists = self._lists _maxes = self._maxes if _maxes: pos = bisect_right(_maxes, value) if pos == len(_maxes): pos -= 1 _lists[pos].append(value) _maxes[pos] = value else: insort(_lists[pos], value) self._expand(pos) else: _lists.append([value]) _maxes.append(value) self._len += 1 def _expand(self, pos): _load = self._load _lists = self._lists _index = self._index if len(_lists[pos]) > (_load << 1): _maxes = self._maxes _lists_pos = _lists[pos] half = _lists_pos[_load:] del _lists_pos[_load:] _maxes[pos] = _lists_pos[-1] _lists.insert(pos + 1, half) _maxes.insert(pos + 1, half[-1]) del _index[:] else: if _index: child = self._offset + pos while child: _index[child] += 1 child = (child - 1) >> 1 _index[0] += 1 def update(self, iterable): _lists = self._lists _maxes = self._maxes values = sorted(iterable) if _maxes: if len(values) * 4 >= self._len: _lists.append(values) values = reduce(iadd, _lists, []) values.sort() self._clear() else: _add = self.add for val in values: _add(val) return _load = self._load _lists.extend(values[pos:(pos + _load)] for pos in range(0, len(values), _load)) _maxes.extend(sublist[-1] for sublist in _lists) self._len = len(values) del self._index[:] _update = update def __contains__(self, value): _maxes = self._maxes if not _maxes: return False pos = bisect_left(_maxes, value) if pos == len(_maxes): return False _lists = self._lists idx = bisect_left(_lists[pos], value) return _lists[pos][idx] == value def discard(self, value): _maxes = self._maxes if not _maxes: return pos = bisect_left(_maxes, value) if pos == len(_maxes): return _lists = self._lists idx = bisect_left(_lists[pos], value) if _lists[pos][idx] == value: self._delete(pos, idx) def remove(self, value): _maxes = self._maxes if not _maxes: raise ValueError('{0!r} not in list'.format(value)) pos = bisect_left(_maxes, value) if pos == len(_maxes): raise ValueError('{0!r} not in list'.format(value)) _lists = self._lists idx = bisect_left(_lists[pos], value) if _lists[pos][idx] == value: self._delete(pos, idx) else: raise ValueError('{0!r} not in list'.format(value)) def _delete(self, pos, idx): _lists = self._lists _maxes = self._maxes _index = self._index _lists_pos = _lists[pos] del _lists_pos[idx] self._len -= 1 len_lists_pos = len(_lists_pos) if len_lists_pos > (self._load >> 1): _maxes[pos] = _lists_pos[-1] if _index: child = self._offset + pos while child > 0: _index[child] -= 1 child = (child - 1) >> 1 _index[0] -= 1 elif len(_lists) > 1: if not pos: pos += 1 prev = pos - 1 _lists[prev].extend(_lists[pos]) _maxes[prev] = _lists[prev][-1] del _lists[pos] del _maxes[pos] del _index[:] self._expand(prev) elif len_lists_pos: _maxes[pos] = _lists_pos[-1] else: del _lists[pos] del _maxes[pos] del _index[:] def _loc(self, pos, idx): if not pos: return idx _index = self._index if not _index: self._build_index() total = 0 pos += self._offset while pos: if not pos & 1: total += _index[pos - 1] pos = (pos - 1) >> 1 return total + idx def _pos(self, idx): if idx < 0: last_len = len(self._lists[-1]) if (-idx) <= last_len: return len(self._lists) - 1, last_len + idx idx += self._len if idx < 0: raise IndexError('list index out of range') elif idx >= self._len: raise IndexError('list index out of range') if idx < len(self._lists[0]): return 0, idx _index = self._index if not _index: self._build_index() pos = 0 child = 1 len_index = len(_index) while child < len_index: index_child = _index[child] if idx < index_child: pos = child else: idx -= index_child pos = child + 1 child = (pos << 1) + 1 return (pos - self._offset, idx) def _build_index(self): row0 = list(map(len, self._lists)) if len(row0) == 1: self._index[:] = row0 self._offset = 0 return head = iter(row0) tail = iter(head) row1 = list(starmap(add, zip(head, tail))) if len(row0) & 1: row1.append(row0[-1]) if len(row1) == 1: self._index[:] = row1 + row0 self._offset = 1 return size = 2 ** (int(log(len(row1) - 1, 2)) + 1) row1.extend(repeat(0, size - len(row1))) tree = [row0, row1] while len(tree[-1]) > 1: head = iter(tree[-1]) tail = iter(head) row = list(starmap(add, zip(head, tail))) tree.append(row) reduce(iadd, reversed(tree), self._index) self._offset = size * 2 - 1 def __delitem__(self, index): if isinstance(index, slice): start, stop, step = index.indices(self._len) if step == 1 and start < stop: if start == 0 and stop == self._len: return self._clear() elif self._len <= 8 * (stop - start): values = self._getitem(slice(None, start)) if stop < self._len: values += self._getitem(slice(stop, None)) self._clear() return self._update(values) indices = range(start, stop, step) # Delete items from greatest index to least so # that the indices remain valid throughout iteration. if step > 0: indices = reversed(indices) _pos, _delete = self._pos, self._delete for index in indices: pos, idx = _pos(index) _delete(pos, idx) else: pos, idx = self._pos(index) self._delete(pos, idx) def __getitem__(self, index): """Lookup value at `index` in sorted list. ``sl.__getitem__(index)`` <==> ``sl[index]`` Supports slicing. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList('abcde') >>> sl[1] 'b' >>> sl[-1] 'e' >>> sl[2:5] ['c', 'd', 'e'] :param index: integer or slice for indexing :return: value or list of values :raises IndexError: if index out of range """ _lists = self._lists if isinstance(index, slice): start, stop, step = index.indices(self._len) if step == 1 and start < stop: # Whole slice optimization: start to stop slices the whole # sorted list. if start == 0 and stop == self._len: return reduce(iadd, self._lists, []) start_pos, start_idx = self._pos(start) start_list = _lists[start_pos] stop_idx = start_idx + stop - start # Small slice optimization: start index and stop index are # within the start list. if len(start_list) >= stop_idx: return start_list[start_idx:stop_idx] if stop == self._len: stop_pos = len(_lists) - 1 stop_idx = len(_lists[stop_pos]) else: stop_pos, stop_idx = self._pos(stop) prefix = _lists[start_pos][start_idx:] middle = _lists[(start_pos + 1):stop_pos] result = reduce(iadd, middle, prefix) result += _lists[stop_pos][:stop_idx] return result if step == -1 and start > stop: result = self._getitem(slice(stop + 1, start + 1)) result.reverse() return result # Return a list because a negative step could # reverse the order of the items and this could # be the desired behavior. indices = range(start, stop, step) return list(self._getitem(index) for index in indices) else: if self._len: if index == 0: return _lists[0][0] elif index == -1: return _lists[-1][-1] else: raise IndexError('list index out of range') if 0 <= index < len(_lists[0]): return _lists[0][index] len_last = len(_lists[-1]) if -len_last < index < 0: return _lists[-1][len_last + index] pos, idx = self._pos(index) return _lists[pos][idx] _getitem = __getitem__ def __setitem__(self, index, value): """Raise not-implemented error. ``sl.__setitem__(index, value)`` <==> ``sl[index] = value`` :raises NotImplementedError: use ``del sl[index]`` and ``sl.add(value)`` instead """ message = 'use ``del sl[index]`` and ``sl.add(value)`` instead' raise NotImplementedError(message) def __iter__(self): """Return an iterator over the sorted list. ``sl.__iter__()`` <==> ``iter(sl)`` Iterating the sorted list while adding or deleting values may raise a :exc:`RuntimeError` or fail to iterate over all values. """ return chain.from_iterable(self._lists) def __reversed__(self): """Return a reverse iterator over the sorted list. ``sl.__reversed__()`` <==> ``reversed(sl)`` Iterating the sorted list while adding or deleting values may raise a :exc:`RuntimeError` or fail to iterate over all values. """ return chain.from_iterable(map(reversed, reversed(self._lists))) def reverse(self): """Raise not-implemented error. Sorted list maintains values in ascending sort order. Values may not be reversed in-place. Use ``reversed(sl)`` for an iterator over values in descending sort order. Implemented to override `MutableSequence.reverse` which provides an erroneous default implementation. :raises NotImplementedError: use ``reversed(sl)`` instead """ raise NotImplementedError('use ``reversed(sl)`` instead') def islice(self, start=None, stop=None, reverse=False): """Return an iterator that slices sorted list from `start` to `stop`. The `start` and `stop` index are treated inclusive and exclusive, respectively. Both `start` and `stop` default to `None` which is automatically inclusive of the beginning and end of the sorted list. When `reverse` is `True` the values are yielded from the iterator in reverse order; `reverse` defaults to `False`. >>> sl = SortedList('abcdefghij') >>> it = sl.islice(2, 6) >>> list(it) ['c', 'd', 'e', 'f'] :param int start: start index (inclusive) :param int stop: stop index (exclusive) :param bool reverse: yield values in reverse order :return: iterator """ _len = self._len if not _len: return iter(()) start, stop, _ = slice(start, stop).indices(self._len) if start >= stop: return iter(()) _pos = self._pos min_pos, min_idx = _pos(start) if stop == _len: max_pos = len(self._lists) - 1 max_idx = len(self._lists[-1]) else: max_pos, max_idx = _pos(stop) return self._islice(min_pos, min_idx, max_pos, max_idx, reverse) def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse): """Return an iterator that slices sorted list using two index pairs. The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the first inclusive and the latter exclusive. See `_pos` for details on how an index is converted to an index pair. When `reverse` is `True`, values are yielded from the iterator in reverse order. """ _lists = self._lists if min_pos > max_pos: return iter(()) if min_pos == max_pos: if reverse: indices = reversed(range(min_idx, max_idx)) return map(_lists[min_pos].__getitem__, indices) indices = range(min_idx, max_idx) return map(_lists[min_pos].__getitem__, indices) next_pos = min_pos + 1 if next_pos == max_pos: if reverse: min_indices = range(min_idx, len(_lists[min_pos])) max_indices = range(max_idx) return chain( map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)), ) min_indices = range(min_idx, len(_lists[min_pos])) max_indices = range(max_idx) return chain( map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices), ) if reverse: min_indices = range(min_idx, len(_lists[min_pos])) sublist_indices = range(next_pos, max_pos) sublists = map(_lists.__getitem__, reversed(sublist_indices)) max_indices = range(max_idx) return chain( map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)), ) min_indices = range(min_idx, len(_lists[min_pos])) sublist_indices = range(next_pos, max_pos) sublists = map(_lists.__getitem__, sublist_indices) max_indices = range(max_idx) return chain( map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices), ) def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False): """Create an iterator of values between `minimum` and `maximum`. Both `minimum` and `maximum` default to `None` which is automatically inclusive of the beginning and end of the sorted list. The argument `inclusive` is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is ``(True, True)`` such that the range is inclusive of both minimum and maximum. When `reverse` is `True` the values are yielded from the iterator in reverse order; `reverse` defaults to `False`. >>> sl = SortedList('abcdefghij') >>> it = sl.irange('c', 'f') >>> list(it) ['c', 'd', 'e', 'f'] :param minimum: minimum value to start iterating :param maximum: maximum value to stop iterating :param inclusive: pair of booleans :param bool reverse: yield values in reverse order :return: iterator """ _maxes = self._maxes if not _maxes: return iter(()) _lists = self._lists # Calculate the minimum (pos, idx) pair. By default this location # will be inclusive in our calculation. if minimum is None: min_pos = 0 min_idx = 0 else: if inclusive[0]: min_pos = bisect_left(_maxes, minimum) if min_pos == len(_maxes): return iter(()) min_idx = bisect_left(_lists[min_pos], minimum) else: min_pos = bisect_right(_maxes, minimum) if min_pos == len(_maxes): return iter(()) min_idx = bisect_right(_lists[min_pos], minimum) # Calculate the maximum (pos, idx) pair. By default this location # will be exclusive in our calculation. if maximum is None: max_pos = len(_maxes) - 1 max_idx = len(_lists[max_pos]) else: if inclusive[1]: max_pos = bisect_right(_maxes, maximum) if max_pos == len(_maxes): max_pos -= 1 max_idx = len(_lists[max_pos]) else: max_idx = bisect_right(_lists[max_pos], maximum) else: max_pos = bisect_left(_maxes, maximum) if max_pos == len(_maxes): max_pos -= 1 max_idx = len(_lists[max_pos]) else: max_idx = bisect_left(_lists[max_pos], maximum) return self._islice(min_pos, min_idx, max_pos, max_idx, reverse) def __len__(self): """Return the size of the sorted list. ``sl.__len__()`` <==> ``len(sl)`` :return: size of sorted list """ return self._len def bisect_left(self, value): """Return an index to insert `value` in the sorted list. If the `value` is already present, the insertion point will be before (to the left of) any existing values. Similar to the `bisect` module in the standard library. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList([10, 11, 12, 13, 14]) >>> sl.bisect_left(12) 2 :param value: insertion index of value in sorted list :return: index """ _maxes = self._maxes if not _maxes: return 0 pos = bisect_left(_maxes, value) if pos == len(_maxes): return self._len idx = bisect_left(self._lists[pos], value) return self._loc(pos, idx) def bisect_right(self, value): """Return an index to insert `value` in the sorted list. Similar to `bisect_left`, but if `value` is already present, the insertion point will be after (to the right of) any existing values. Similar to the `bisect` module in the standard library. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList([10, 11, 12, 13, 14]) >>> sl.bisect_right(12) 3 :param value: insertion index of value in sorted list :return: index """ _maxes = self._maxes if not _maxes: return 0 pos = bisect_right(_maxes, value) if pos == len(_maxes): return self._len idx = bisect_right(self._lists[pos], value) return self._loc(pos, idx) bisect = bisect_right _bisect_right = bisect_right def count(self, value): """Return number of occurrences of `value` in the sorted list. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4]) >>> sl.count(3) 3 :param value: value to count in sorted list :return: count """ _maxes = self._maxes if not _maxes: return 0 pos_left = bisect_left(_maxes, value) if pos_left == len(_maxes): return 0 _lists = self._lists idx_left = bisect_left(_lists[pos_left], value) pos_right = bisect_right(_maxes, value) if pos_right == len(_maxes): return self._len - self._loc(pos_left, idx_left) idx_right = bisect_right(_lists[pos_right], value) if pos_left == pos_right: return idx_right - idx_left right = self._loc(pos_right, idx_right) left = self._loc(pos_left, idx_left) return right - left def copy(self): """Return a shallow copy of the sorted list. Runtime complexity: `O(n)` :return: new sorted list """ return self.__class__(self) __copy__ = copy def append(self, value): """Raise not-implemented error. Implemented to override `MutableSequence.append` which provides an erroneous default implementation. :raises NotImplementedError: use ``sl.add(value)`` instead """ raise NotImplementedError('use ``sl.add(value)`` instead') def extend(self, values): """Raise not-implemented error. Implemented to override `MutableSequence.extend` which provides an erroneous default implementation. :raises NotImplementedError: use ``sl.update(values)`` instead """ raise NotImplementedError('use ``sl.update(values)`` instead') def insert(self, index, value): """Raise not-implemented error. :raises NotImplementedError: use ``sl.add(value)`` instead """ raise NotImplementedError('use ``sl.add(value)`` instead') def pop(self, index=-1): """Remove and return value at `index` in sorted list. Raise :exc:`IndexError` if the sorted list is empty or index is out of range. Negative indices are supported. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList('abcde') >>> sl.pop() 'e' >>> sl.pop(2) 'c' >>> sl SortedList(['a', 'b', 'd']) :param int index: index of value (default -1) :return: value :raises IndexError: if index is out of range """ if not self._len: raise IndexError('pop index out of range') _lists = self._lists if index == 0: val = _lists[0][0] self._delete(0, 0) return val if index == -1: pos = len(_lists) - 1 loc = len(_lists[pos]) - 1 val = _lists[pos][loc] self._delete(pos, loc) return val if 0 <= index < len(_lists[0]): val = _lists[0][index] self._delete(0, index) return val len_last = len(_lists[-1]) if -len_last < index < 0: pos = len(_lists) - 1 loc = len_last + index val = _lists[pos][loc] self._delete(pos, loc) return val pos, idx = self._pos(index) val = _lists[pos][idx] self._delete(pos, idx) return val def index(self, value, start=None, stop=None): """Return first index of value in sorted list. Raise ValueError if `value` is not present. Index must be between `start` and `stop` for the `value` to be considered present. The default value, None, for `start` and `stop` indicate the beginning and end of the sorted list. Negative indices are supported. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList('abcde') >>> sl.index('d') 3 >>> sl.index('z') Traceback (most recent call last): ... ValueError: 'z' is not in list :param value: value in sorted list :param int start: start index (default None, start of sorted list) :param int stop: stop index (default None, end of sorted list) :return: index of value :raises ValueError: if value is not present """ _len = self._len if not _len: raise ValueError('{0!r} is not in list'.format(value)) if start is None: start = 0 if start < 0: start += _len if start < 0: start = 0 if stop is None: stop = _len if stop < 0: stop += _len if stop > _len: stop = _len if stop <= start: raise ValueError('{0!r} is not in list'.format(value)) _maxes = self._maxes pos_left = bisect_left(_maxes, value) if pos_left == len(_maxes): raise ValueError('{0!r} is not in list'.format(value)) _lists = self._lists idx_left = bisect_left(_lists[pos_left], value) if _lists[pos_left][idx_left] != value: raise ValueError('{0!r} is not in list'.format(value)) stop -= 1 left = self._loc(pos_left, idx_left) if start <= left: if left <= stop: return left else: right = self._bisect_right(value) - 1 if start <= right: return start raise ValueError('{0!r} is not in list'.format(value)) def __add__(self, other): """Return new sorted list containing all values in both sequences. ``sl.__add__(other)`` <==> ``sl + other`` Values in `other` do not need to be in sorted order. Runtime complexity: `O(n*log(n))` >>> sl1 = SortedList('bat') >>> sl2 = SortedList('cat') >>> sl1 + sl2 SortedList(['a', 'a', 'b', 'c', 't', 't']) :param other: other iterable :return: new sorted list """ values = reduce(iadd, self._lists, []) values.extend(other) return self.__class__(values) __radd__ = __add__ def __iadd__(self, other): """Update sorted list with values from `other`. ``sl.__iadd__(other)`` <==> ``sl += other`` Values in `other` do not need to be in sorted order. Runtime complexity: `O(k*log(n))` -- approximate. >>> sl = SortedList('bat') >>> sl += 'cat' >>> sl SortedList(['a', 'a', 'b', 'c', 't', 't']) :param other: other iterable :return: existing sorted list """ self._update(other) return self def __mul__(self, num): """Return new sorted list with `num` shallow copies of values. ``sl.__mul__(num)`` <==> ``sl * num`` Runtime complexity: `O(n*log(n))` >>> sl = SortedList('abc') >>> sl * 3 SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']) :param int num: count of shallow copies :return: new sorted list """ values = reduce(iadd, self._lists, []) * num return self.__class__(values) __rmul__ = __mul__ def __imul__(self, num): """Update the sorted list with `num` shallow copies of values. ``sl.__imul__(num)`` <==> ``sl *= num`` Runtime complexity: `O(n*log(n))` >>> sl = SortedList('abc') >>> sl *= 3 >>> sl SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c']) :param int num: count of shallow copies :return: existing sorted list """ values = reduce(iadd, self._lists, []) * num self._clear() self._update(values) return self def __make_cmp(seq_op, symbol, doc): "Make comparator method." def comparer(self, other): "Compare method for sorted list and sequence." if not isinstance(other, Sequence): return NotImplemented self_len = self._len len_other = len(other) if self_len != len_other: if seq_op is eq: return False if seq_op is ne: return True for alpha, beta in zip(self, other): if alpha != beta: return seq_op(alpha, beta) return seq_op(self_len, len_other) seq_op_name = seq_op.__name__ comparer.__name__ = '__{0}__'.format(seq_op_name) doc_str = """Return true if and only if sorted list is {0} `other`. ``sl.__{1}__(other)`` <==> ``sl {2} other`` Comparisons use lexicographical order as with sequences. Runtime complexity: `O(n)` :param other: `other` sequence :return: true if sorted list is {0} `other` """ comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol)) return comparer __eq__ = __make_cmp(eq, '==', 'equal to') __ne__ = __make_cmp(ne, '!=', 'not equal to') __lt__ = __make_cmp(lt, '<', 'less than') __gt__ = __make_cmp(gt, '>', 'greater than') __le__ = __make_cmp(le, '<=', 'less than or equal to') __ge__ = __make_cmp(ge, '>=', 'greater than or equal to') __make_cmp = staticmethod(__make_cmp) def __reduce__(self): values = reduce(iadd, self._lists, []) return (type(self), (values,)) @recursive_repr() def __repr__(self): """Return string representation of sorted list. ``sl.__repr__()`` <==> ``repr(sl)`` :return: string representation """ return '{0}({1!r})'.format(type(self).__name__, list(self)) def _check(self): """Check invariants of sorted list. Runtime complexity: `O(n)` """ try: assert self._load >= 4 assert len(self._maxes) == len(self._lists) assert self._len == sum(len(sublist) for sublist in self._lists) # Check all sublists are sorted. for sublist in self._lists: for pos in range(1, len(sublist)): assert sublist[pos - 1] <= sublist[pos] # Check beginning/end of sublists are sorted. for pos in range(1, len(self._lists)): assert self._lists[pos - 1][-1] <= self._lists[pos][0] # Check _maxes index is the last value of each sublist. for pos in range(len(self._maxes)): assert self._maxes[pos] == self._lists[pos][-1] # Check sublist lengths are less than double load-factor. double = self._load << 1 assert all(len(sublist) <= double for sublist in self._lists) # Check sublist lengths are greater than half load-factor for all # but the last sublist. half = self._load >> 1 for pos in range(0, len(self._lists) - 1): assert len(self._lists[pos]) >= half if self._index: assert self._len == self._index[0] assert len(self._index) == self._offset + len(self._lists) # Check index leaf nodes equal length of sublists. for pos in range(len(self._lists)): leaf = self._index[self._offset + pos] assert leaf == len(self._lists[pos]) # Check index branch nodes are the sum of their children. for pos in range(self._offset): child = (pos << 1) + 1 if child >= len(self._index): assert self._index[pos] == 0 elif child + 1 == len(self._index): assert self._index[pos] == self._index[child] else: child_sum = self._index[child] + self._index[child + 1] assert child_sum == self._index[pos] except: traceback.print_exc(file=sys.stdout) print('len', self._len) print('load', self._load) print('offset', self._offset) print('len_index', len(self._index)) print('index', self._index) print('len_maxes', len(self._maxes)) print('maxes', self._maxes) print('len_lists', len(self._lists)) print('lists', self._lists) raise def identity(value): "Identity function." return value class SortedKeyList(SortedList): """Sorted-key list is a subtype of sorted list. The sorted-key list maintains values in comparison order based on the result of a key function applied to every value. All the same methods that are available in :class:`SortedList` are also available in :class:`SortedKeyList`. Additional methods provided: * :attr:`SortedKeyList.key` * :func:`SortedKeyList.bisect_key_left` * :func:`SortedKeyList.bisect_key_right` * :func:`SortedKeyList.irange_key` Some examples below use: >>> from operator import neg >>> neg >>> neg(1) -1 """ def __init__(self, iterable=None, key=identity): """Initialize sorted-key list instance. Optional `iterable` argument provides an initial iterable of values to initialize the sorted-key list. Optional `key` argument defines a callable that, like the `key` argument to Python's `sorted` function, extracts a comparison key from each value. The default is the identity function. Runtime complexity: `O(n*log(n))` >>> from operator import neg >>> skl = SortedKeyList(key=neg) >>> skl SortedKeyList([], key=) >>> skl = SortedKeyList([3, 1, 2], key=neg) >>> skl SortedKeyList([3, 2, 1], key=) :param iterable: initial values (optional) :param key: function used to extract comparison key (optional) """ self._key = key self._len = 0 self._load = self.DEFAULT_LOAD_FACTOR self._lists = [] self._keys = [] self._maxes = [] self._index = [] self._offset = 0 if iterable is not None: self._update(iterable) def __new__(cls, iterable=None, key=identity): return object.__new__(cls) @property def key(self): "Function used to extract comparison key from values." return self._key def clear(self): """Remove all values from sorted-key list. Runtime complexity: `O(n)` """ self._len = 0 del self._lists[:] del self._keys[:] del self._maxes[:] del self._index[:] _clear = clear def add(self, value): """Add `value` to sorted-key list. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList(key=neg) >>> skl.add(3) >>> skl.add(1) >>> skl.add(2) >>> skl SortedKeyList([3, 2, 1], key=) :param value: value to add to sorted-key list """ _lists = self._lists _keys = self._keys _maxes = self._maxes key = self._key(value) if _maxes: pos = bisect_right(_maxes, key) if pos == len(_maxes): pos -= 1 _lists[pos].append(value) _keys[pos].append(key) _maxes[pos] = key else: idx = bisect_right(_keys[pos], key) _lists[pos].insert(idx, value) _keys[pos].insert(idx, key) self._expand(pos) else: _lists.append([value]) _keys.append([key]) _maxes.append(key) self._len += 1 def _expand(self, pos): """Split sublists with length greater than double the load-factor. Updates the index when the sublist length is less than double the load level. This requires incrementing the nodes in a traversal from the leaf node to the root. For an example traversal see ``SortedList._loc``. """ _lists = self._lists _keys = self._keys _index = self._index if len(_keys[pos]) > (self._load << 1): _maxes = self._maxes _load = self._load _lists_pos = _lists[pos] _keys_pos = _keys[pos] half = _lists_pos[_load:] half_keys = _keys_pos[_load:] del _lists_pos[_load:] del _keys_pos[_load:] _maxes[pos] = _keys_pos[-1] _lists.insert(pos + 1, half) _keys.insert(pos + 1, half_keys) _maxes.insert(pos + 1, half_keys[-1]) del _index[:] else: if _index: child = self._offset + pos while child: _index[child] += 1 child = (child - 1) >> 1 _index[0] += 1 def update(self, iterable): """Update sorted-key list by adding all values from `iterable`. Runtime complexity: `O(k*log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList(key=neg) >>> skl.update([3, 1, 2]) >>> skl SortedKeyList([3, 2, 1], key=) :param iterable: iterable of values to add """ _lists = self._lists _keys = self._keys _maxes = self._maxes values = sorted(iterable, key=self._key) if _maxes: if len(values) * 4 >= self._len: _lists.append(values) values = reduce(iadd, _lists, []) values.sort(key=self._key) self._clear() else: _add = self.add for val in values: _add(val) return _load = self._load _lists.extend(values[pos:(pos + _load)] for pos in range(0, len(values), _load)) _keys.extend(list(map(self._key, _list)) for _list in _lists) _maxes.extend(sublist[-1] for sublist in _keys) self._len = len(values) del self._index[:] _update = update def __contains__(self, value): """Return true if `value` is an element of the sorted-key list. ``skl.__contains__(value)`` <==> ``value in skl`` Runtime complexity: `O(log(n))` >>> from operator import neg >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg) >>> 3 in skl True :param value: search for value in sorted-key list :return: true if `value` in sorted-key list """ _maxes = self._maxes if not _maxes: return False key = self._key(value) pos = bisect_left(_maxes, key) if pos == len(_maxes): return False _lists = self._lists _keys = self._keys idx = bisect_left(_keys[pos], key) len_keys = len(_keys) len_sublist = len(_keys[pos]) while True: if _keys[pos][idx] != key: return False if _lists[pos][idx] == value: return True idx += 1 if idx == len_sublist: pos += 1 if pos == len_keys: return False len_sublist = len(_keys[pos]) idx = 0 def discard(self, value): """Remove `value` from sorted-key list if it is a member. If `value` is not a member, do nothing. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg) >>> skl.discard(1) >>> skl.discard(0) >>> skl == [5, 4, 3, 2] True :param value: `value` to discard from sorted-key list """ _maxes = self._maxes if not _maxes: return key = self._key(value) pos = bisect_left(_maxes, key) if pos == len(_maxes): return _lists = self._lists _keys = self._keys idx = bisect_left(_keys[pos], key) len_keys = len(_keys) len_sublist = len(_keys[pos]) while True: if _keys[pos][idx] != key: return if _lists[pos][idx] == value: self._delete(pos, idx) return idx += 1 if idx == len_sublist: pos += 1 if pos == len_keys: return len_sublist = len(_keys[pos]) idx = 0 def remove(self, value): """Remove `value` from sorted-key list; `value` must be a member. If `value` is not a member, raise ValueError. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg) >>> skl.remove(5) >>> skl == [4, 3, 2, 1] True >>> skl.remove(0) Traceback (most recent call last): ... ValueError: 0 not in list :param value: `value` to remove from sorted-key list :raises ValueError: if `value` is not in sorted-key list """ _maxes = self._maxes if not _maxes: raise ValueError('{0!r} not in list'.format(value)) key = self._key(value) pos = bisect_left(_maxes, key) if pos == len(_maxes): raise ValueError('{0!r} not in list'.format(value)) _lists = self._lists _keys = self._keys idx = bisect_left(_keys[pos], key) len_keys = len(_keys) len_sublist = len(_keys[pos]) while True: if _keys[pos][idx] != key: raise ValueError('{0!r} not in list'.format(value)) if _lists[pos][idx] == value: self._delete(pos, idx) return idx += 1 if idx == len_sublist: pos += 1 if pos == len_keys: raise ValueError('{0!r} not in list'.format(value)) len_sublist = len(_keys[pos]) idx = 0 def _delete(self, pos, idx): """Delete value at the given `(pos, idx)`. Combines lists that are less than half the load level. Updates the index when the sublist length is more than half the load level. This requires decrementing the nodes in a traversal from the leaf node to the root. For an example traversal see ``SortedList._loc``. :param int pos: lists index :param int idx: sublist index """ _lists = self._lists _keys = self._keys _maxes = self._maxes _index = self._index keys_pos = _keys[pos] lists_pos = _lists[pos] del keys_pos[idx] del lists_pos[idx] self._len -= 1 len_keys_pos = len(keys_pos) if len_keys_pos > (self._load >> 1): _maxes[pos] = keys_pos[-1] if _index: child = self._offset + pos while child > 0: _index[child] -= 1 child = (child - 1) >> 1 _index[0] -= 1 elif len(_keys) > 1: if not pos: pos += 1 prev = pos - 1 _keys[prev].extend(_keys[pos]) _lists[prev].extend(_lists[pos]) _maxes[prev] = _keys[prev][-1] del _lists[pos] del _keys[pos] del _maxes[pos] del _index[:] self._expand(prev) elif len_keys_pos: _maxes[pos] = keys_pos[-1] else: del _lists[pos] del _keys[pos] del _maxes[pos] del _index[:] def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False): """Create an iterator of values between `minimum` and `maximum`. Both `minimum` and `maximum` default to `None` which is automatically inclusive of the beginning and end of the sorted-key list. The argument `inclusive` is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is ``(True, True)`` such that the range is inclusive of both minimum and maximum. When `reverse` is `True` the values are yielded from the iterator in reverse order; `reverse` defaults to `False`. >>> from operator import neg >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg) >>> it = skl.irange(14.5, 11.5) >>> list(it) [14, 13, 12] :param minimum: minimum value to start iterating :param maximum: maximum value to stop iterating :param inclusive: pair of booleans :param bool reverse: yield values in reverse order :return: iterator """ min_key = self._key(minimum) if minimum is not None else None max_key = self._key(maximum) if maximum is not None else None return self._irange_key( min_key=min_key, max_key=max_key, inclusive=inclusive, reverse=reverse, ) def irange_key(self, min_key=None, max_key=None, inclusive=(True, True), reverse=False): """Create an iterator of values between `min_key` and `max_key`. Both `min_key` and `max_key` default to `None` which is automatically inclusive of the beginning and end of the sorted-key list. The argument `inclusive` is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is ``(True, True)`` such that the range is inclusive of both minimum and maximum. When `reverse` is `True` the values are yielded from the iterator in reverse order; `reverse` defaults to `False`. >>> from operator import neg >>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg) >>> it = skl.irange_key(-14, -12) >>> list(it) [14, 13, 12] :param min_key: minimum key to start iterating :param max_key: maximum key to stop iterating :param inclusive: pair of booleans :param bool reverse: yield values in reverse order :return: iterator """ _maxes = self._maxes if not _maxes: return iter(()) _keys = self._keys # Calculate the minimum (pos, idx) pair. By default this location # will be inclusive in our calculation. if min_key is None: min_pos = 0 min_idx = 0 else: if inclusive[0]: min_pos = bisect_left(_maxes, min_key) if min_pos == len(_maxes): return iter(()) min_idx = bisect_left(_keys[min_pos], min_key) else: min_pos = bisect_right(_maxes, min_key) if min_pos == len(_maxes): return iter(()) min_idx = bisect_right(_keys[min_pos], min_key) # Calculate the maximum (pos, idx) pair. By default this location # will be exclusive in our calculation. if max_key is None: max_pos = len(_maxes) - 1 max_idx = len(_keys[max_pos]) else: if inclusive[1]: max_pos = bisect_right(_maxes, max_key) if max_pos == len(_maxes): max_pos -= 1 max_idx = len(_keys[max_pos]) else: max_idx = bisect_right(_keys[max_pos], max_key) else: max_pos = bisect_left(_maxes, max_key) if max_pos == len(_maxes): max_pos -= 1 max_idx = len(_keys[max_pos]) else: max_idx = bisect_left(_keys[max_pos], max_key) return self._islice(min_pos, min_idx, max_pos, max_idx, reverse) _irange_key = irange_key def bisect_left(self, value): """Return an index to insert `value` in the sorted-key list. If the `value` is already present, the insertion point will be before (to the left of) any existing values. Similar to the `bisect` module in the standard library. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg) >>> skl.bisect_left(1) 4 :param value: insertion index of value in sorted-key list :return: index """ return self._bisect_key_left(self._key(value)) def bisect_right(self, value): """Return an index to insert `value` in the sorted-key list. Similar to `bisect_left`, but if `value` is already present, the insertion point will be after (to the right of) any existing values. Similar to the `bisect` module in the standard library. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedList([5, 4, 3, 2, 1], key=neg) >>> skl.bisect_right(1) 5 :param value: insertion index of value in sorted-key list :return: index """ return self._bisect_key_right(self._key(value)) bisect = bisect_right def bisect_key_left(self, key): """Return an index to insert `key` in the sorted-key list. If the `key` is already present, the insertion point will be before (to the left of) any existing keys. Similar to the `bisect` module in the standard library. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg) >>> skl.bisect_key_left(-1) 4 :param key: insertion index of key in sorted-key list :return: index """ _maxes = self._maxes if not _maxes: return 0 pos = bisect_left(_maxes, key) if pos == len(_maxes): return self._len idx = bisect_left(self._keys[pos], key) return self._loc(pos, idx) _bisect_key_left = bisect_key_left def bisect_key_right(self, key): """Return an index to insert `key` in the sorted-key list. Similar to `bisect_key_left`, but if `key` is already present, the insertion point will be after (to the right of) any existing keys. Similar to the `bisect` module in the standard library. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedList([5, 4, 3, 2, 1], key=neg) >>> skl.bisect_key_right(-1) 5 :param key: insertion index of key in sorted-key list :return: index """ _maxes = self._maxes if not _maxes: return 0 pos = bisect_right(_maxes, key) if pos == len(_maxes): return self._len idx = bisect_right(self._keys[pos], key) return self._loc(pos, idx) bisect_key = bisect_key_right _bisect_key_right = bisect_key_right def count(self, value): """Return number of occurrences of `value` in the sorted-key list. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg) >>> skl.count(2) 2 :param value: value to count in sorted-key list :return: count """ _maxes = self._maxes if not _maxes: return 0 key = self._key(value) pos = bisect_left(_maxes, key) if pos == len(_maxes): return 0 _lists = self._lists _keys = self._keys idx = bisect_left(_keys[pos], key) total = 0 len_keys = len(_keys) len_sublist = len(_keys[pos]) while True: if _keys[pos][idx] != key: return total if _lists[pos][idx] == value: total += 1 idx += 1 if idx == len_sublist: pos += 1 if pos == len_keys: return total len_sublist = len(_keys[pos]) idx = 0 def copy(self): """Return a shallow copy of the sorted-key list. Runtime complexity: `O(n)` :return: new sorted-key list """ return self.__class__(self, key=self._key) __copy__ = copy def index(self, value, start=None, stop=None): """Return first index of value in sorted-key list. Raise ValueError if `value` is not present. Index must be between `start` and `stop` for the `value` to be considered present. The default value, None, for `start` and `stop` indicate the beginning and end of the sorted-key list. Negative indices are supported. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg) >>> skl.index(2) 3 >>> skl.index(0) Traceback (most recent call last): ... ValueError: 0 is not in list :param value: value in sorted-key list :param int start: start index (default None, start of sorted-key list) :param int stop: stop index (default None, end of sorted-key list) :return: index of value :raises ValueError: if value is not present """ _len = self._len if not _len: raise ValueError('{0!r} is not in list'.format(value)) if start is None: start = 0 if start < 0: start += _len if start < 0: start = 0 if stop is None: stop = _len if stop < 0: stop += _len if stop > _len: stop = _len if stop <= start: raise ValueError('{0!r} is not in list'.format(value)) _maxes = self._maxes key = self._key(value) pos = bisect_left(_maxes, key) if pos == len(_maxes): raise ValueError('{0!r} is not in list'.format(value)) stop -= 1 _lists = self._lists _keys = self._keys idx = bisect_left(_keys[pos], key) len_keys = len(_keys) len_sublist = len(_keys[pos]) while True: if _keys[pos][idx] != key: raise ValueError('{0!r} is not in list'.format(value)) if _lists[pos][idx] == value: loc = self._loc(pos, idx) if start <= loc <= stop: return loc elif loc > stop: break idx += 1 if idx == len_sublist: pos += 1 if pos == len_keys: raise ValueError('{0!r} is not in list'.format(value)) len_sublist = len(_keys[pos]) idx = 0 raise ValueError('{0!r} is not in list'.format(value)) def __add__(self, other): """Return new sorted-key list containing all values in both sequences. ``skl.__add__(other)`` <==> ``skl + other`` Values in `other` do not need to be in sorted-key order. Runtime complexity: `O(n*log(n))` >>> from operator import neg >>> skl1 = SortedKeyList([5, 4, 3], key=neg) >>> skl2 = SortedKeyList([2, 1, 0], key=neg) >>> skl1 + skl2 SortedKeyList([5, 4, 3, 2, 1, 0], key=) :param other: other iterable :return: new sorted-key list """ values = reduce(iadd, self._lists, []) values.extend(other) return self.__class__(values, key=self._key) __radd__ = __add__ def __mul__(self, num): """Return new sorted-key list with `num` shallow copies of values. ``skl.__mul__(num)`` <==> ``skl * num`` Runtime complexity: `O(n*log(n))` >>> from operator import neg >>> skl = SortedKeyList([3, 2, 1], key=neg) >>> skl * 2 SortedKeyList([3, 3, 2, 2, 1, 1], key=) :param int num: count of shallow copies :return: new sorted-key list """ values = reduce(iadd, self._lists, []) * num return self.__class__(values, key=self._key) def __reduce__(self): values = reduce(iadd, self._lists, []) return (type(self), (values, self.key)) @recursive_repr() def __repr__(self): """Return string representation of sorted-key list. ``skl.__repr__()`` <==> ``repr(skl)`` :return: string representation """ type_name = type(self).__name__ return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key) def _check(self): """Check invariants of sorted-key list. Runtime complexity: `O(n)` """ try: assert self._load >= 4 assert len(self._maxes) == len(self._lists) == len(self._keys) assert self._len == sum(len(sublist) for sublist in self._lists) # Check all sublists are sorted. for sublist in self._keys: for pos in range(1, len(sublist)): assert sublist[pos - 1] <= sublist[pos] # Check beginning/end of sublists are sorted. for pos in range(1, len(self._keys)): assert self._keys[pos - 1][-1] <= self._keys[pos][0] # Check _keys matches _key mapped to _lists. for val_sublist, key_sublist in zip(self._lists, self._keys): assert len(val_sublist) == len(key_sublist) for val, key in zip(val_sublist, key_sublist): assert self._key(val) == key # Check _maxes index is the last value of each sublist. for pos in range(len(self._maxes)): assert self._maxes[pos] == self._keys[pos][-1] # Check sublist lengths are less than double load-factor. double = self._load << 1 assert all(len(sublist) <= double for sublist in self._lists) # Check sublist lengths are greater than half load-factor for all # but the last sublist. half = self._load >> 1 for pos in range(0, len(self._lists) - 1): assert len(self._lists[pos]) >= half if self._index: assert self._len == self._index[0] assert len(self._index) == self._offset + len(self._lists) # Check index leaf nodes equal length of sublists. for pos in range(len(self._lists)): leaf = self._index[self._offset + pos] assert leaf == len(self._lists[pos]) # Check index branch nodes are the sum of their children. for pos in range(self._offset): child = (pos << 1) + 1 if child >= len(self._index): assert self._index[pos] == 0 elif child + 1 == len(self._index): assert self._index[pos] == self._index[child] else: child_sum = self._index[child] + self._index[child + 1] assert child_sum == self._index[pos] except: traceback.print_exc(file=sys.stdout) print('len', self._len) print('load', self._load) print('offset', self._offset) print('len_index', len(self._index)) print('index', self._index) print('len_maxes', len(self._maxes)) print('maxes', self._maxes) print('len_keys', len(self._keys)) print('keys', self._keys) print('len_lists', len(self._lists)) print('lists', self._lists) raise SortedListWithKey = SortedKeyList N=int(input()) A=list(map(int,input().split())) def solve(X): S=SortedList(X) MAXX=S[-1] S.discard(MAXX) while len(S)>1: MIN=S[0] MAX=S[-1] S.discard(MIN) S.discard(MAX) S.add(MIN+MAX) if S[0]<=0 and MAXX>=0: return True else: return False if solve(A) or solve(list(map(lambda x:-x,A))): print("Yes") else: print("No")