"""Sorted List

==============

:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted

collections library, written in pure-Python, and fast as C-extensions. The

:doc:`introduction<introduction>` is the best way to get started.

Sorted list implementations:

.. currentmodule:: sortedcontainers

* :class:`SortedList`

* :class:`SortedKeyList`

"""

# pylint: disable=too-many-lines

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

###############################################################################

# BEGIN Python 2/3 Shims

###############################################################################

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='...'):

"Decorator to make a repr function return fillvalue for a recursive call."

# pylint: disable=missing-docstring

# Copied from reprlib in Python 3

# https://hg.python.org/cpython/file/3.6/Lib/reprlib.py

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

###############################################################################

# END Python 2/3 Shims

###############################################################################

class SortedList(MutableSequence):

"""Sorted list is a sorted mutable sequence.

Sorted list values are maintained in sorted order.

Sorted list values must be comparable. The total ordering of values must

not change while they are stored in the sorted list.

Methods for adding values:

* :func:`SortedList.add`

* :func:`SortedList.update`

* :func:`SortedList.__add__`

* :func:`SortedList.__iadd__`

* :func:`SortedList.__mul__`

* :func:`SortedList.__imul__`

Methods for removing values:

* :func:`SortedList.clear`

* :func:`SortedList.discard`

* :func:`SortedList.remove`

* :func:`SortedList.pop`

* :func:`SortedList.__delitem__`

Methods for looking up values:

* :func:`SortedList.bisect_left`

* :func:`SortedList.bisect_right`

* :func:`SortedList.count`

* :func:`SortedList.index`

* :func:`SortedList.__contains__`

* :func:`SortedList.__getitem__`

Methods for iterating values:

* :func:`SortedList.irange`

* :func:`SortedList.islice`

* :func:`SortedList.__iter__`

* :func:`SortedList.__reversed__`

Methods for miscellany:

* :func:`SortedList.copy`

* :func:`SortedList.__len__`

* :func:`SortedList.__repr__`

* :func:`SortedList._check`

* :func:`SortedList._reset`

Sorted lists use lexicographical ordering semantics when compared to other

sequences.

Some methods of mutable sequences are not supported and will raise

not-implemented error.

"""

DEFAULT_LOAD_FACTOR = 1000

def __init__(self, iterable=None, key=None):

"""Initialize sorted list instance.

Optional `iterable` argument provides an initial iterable of values to

initialize the sorted list.

Runtime complexity: `O(n*log(n))`

>>> sl = SortedList()

>>> sl

SortedList([])

>>> sl = SortedList([3, 1, 2, 5, 4])

>>> sl

SortedList([1, 2, 3, 4, 5])

:param iterable: initial values (optional)

"""

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):

"""Create new sorted list or sorted-key list instance.

Optional `key`-function argument will return an instance of subtype

:class:`SortedKeyList`.

>>> sl = SortedList()

>>> isinstance(sl, SortedList)

True

>>> sl = SortedList(key=lambda x: -x)

>>> isinstance(sl, SortedList)

True

>>> isinstance(sl, SortedKeyList)

True

:param iterable: initial values (optional)

:param key: function used to extract comparison key (optional)

:return: sorted list or sorted-key list instance

"""

# pylint: disable=unused-argument

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

"""Function used to extract comparison key from values.

Sorted list compares values directly so the key function is none.

"""

return None

def _reset(self, load):

"""Reset sorted list load factor.

The `load` specifies the load-factor of the list. The default load

factor of 1000 works well for lists from tens to tens-of-millions of

values. Good practice is to use a value that is the cube root of the

list size. With billions of elements, the best load factor depends on

your usage. It's best to leave the load factor at the default until you

start benchmarking.

See :doc:`implementation` and :doc:`performance-scale` for more

information.

Runtime complexity: `O(n)`

:param int load: load-factor for sorted list sublists

"""

values = reduce(iadd, self._lists, [])

self._clear()

self._load = load

self._update(values)

def clear(self):

"""Remove all values from sorted list.

Runtime complexity: `O(n)`

"""

self._len = 0

del self._lists[:]

del self._maxes[:]

del self._index[:]

self._offset = 0

_clear = clear

def add(self, value):

"""Add `value` to sorted list.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList()

>>> sl.add(3)

>>> sl.add(1)

>>> sl.add(2)

>>> sl

SortedList([1, 2, 3])

:param value: value to add to sorted list

"""

_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):

"""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``.

"""

_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):

"""Update sorted list by adding all values from `iterable`.

Runtime complexity: `O(k*log(n))` -- approximate.

>>> sl = SortedList()

>>> sl.update([3, 1, 2])

>>> sl

SortedList([1, 2, 3])

:param iterable: iterable of values to add

"""

_lists = self._lists

_maxes = self._maxes

values = sorted(iterable)

if _maxes:

if len(values) * 4 >= self._len:

values.extend(chain.from_iterable(_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):

"""Return true if `value` is an element of the sorted list.

``sl.__contains__(value)`` <==> ``value in sl``

Runtime complexity: `O(log(n))`

>>> sl = SortedList([1, 2, 3, 4, 5])

>>> 3 in sl

True

:param value: search for value in sorted list

:return: true if `value` in sorted list

"""

_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):

"""Remove `value` from sorted list if it is a member.

If `value` is not a member, do nothing.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList([1, 2, 3, 4, 5])

>>> sl.discard(5)

>>> sl.discard(0)

>>> sl == [1, 2, 3, 4]

True

:param value: `value` to discard from sorted list

"""

_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):

"""Remove `value` from sorted list; `value` must be a member.

If `value` is not a member, raise ValueError.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList([1, 2, 3, 4, 5])

>>> sl.remove(5)

>>> sl == [1, 2, 3, 4]

True

>>> sl.remove(0)

Traceback (most recent call last):

...

ValueError: 0 not in list

:param value: `value` to remove from sorted list

:raises ValueError: if `value` is not in sorted list

"""

_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):

"""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

_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):

"""Convert an index pair (lists index, sublist index) into a single

index number that corresponds to the position of the value in the

sorted list.

Many queries require the index be built. Details of the index are

described in ``SortedList._build_index``.

Indexing requires traversing the tree from a leaf node to the root. The

parent of each node is easily computable at ``(pos - 1) // 2``.

Left-child nodes are always at odd indices and right-child nodes are

always at even indices.

When traversing up from a right-child node, increment the total by the

left-child node.

The final index is the sum from traversal and the index in the sublist.

For example, using the index from ``SortedList._build_index``::

_index = 14 5 9 3 2 4 5

_offset = 3

Tree::

14

5 9

3 2 4 5

Converting an index pair (2, 3) into a single index involves iterating

like so:

1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify

the node as a left-child node. At such nodes, we simply traverse to

the parent.

2. At node 9, position 2, we recognize the node as a right-child node

and accumulate the left-child in our total. Total is now 5 and we

traverse to the parent at position 0.

3. Iteration ends at the root.

The index is then the sum of the total and sublist index: 5 + 3 = 8.

:param int pos: lists index

:param int idx: sublist index

:return: index in sorted list

"""

if not pos:

return idx

_index = self._index

if not _index:

self._build_index()

total = 0

# Increment pos to point in the index to len(self._lists[pos]).

pos += self._offset

# Iterate until reaching the root of the index tree at pos = 0.

while pos:

# Right-child nodes are at odd indices. At such indices

# account the total below the left child node.

if not pos & 1:

total += _index[pos - 1]

# Advance pos to the parent node.

pos = (pos - 1) >> 1

return total + idx

def _pos(self, idx):

"""Convert an index into an index pair (lists index, sublist index)

that can be used to access the corresponding lists position.

Many queries require the index be built. Details of the index are

described in ``SortedList._build_index``.

Indexing requires traversing the tree to a leaf node. Each node has two

children which are easily computable. Given an index, pos, the

left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +

2``.

When the index is less than the left-child, traversal moves to the

left sub-tree. Otherwise, the index is decremented by the left-child

and traversal moves to the right sub-tree.

At a child node, the indexing pair is computed from the relative

position of the child node as compared with the offset and the remaining

index.

For example, using the index from ``SortedList._build_index``::

_index = 14 5 9 3 2 4 5

_offset = 3

Tree::

14

5 9

3 2 4 5

Indexing position 8 involves iterating like so:

1. Starting at the root, position 0, 8 is compared with the left-child

node (5) which it is greater than. When greater the index is

decremented and the position is updated to the right child node.

2. At node 9 with index 3, we again compare the index to the left-child

node with value 4. Because the index is the less than the left-child

node, we simply traverse to the left.

3. At node 4 with index 3, we recognize that we are at a leaf node and

stop iterating.

4. To compute the sublist index, we subtract the offset from the index

of the leaf node: 5 - 3 = 2. To compute the index in the sublist, we

simply use the index remaining from iteration. In this case, 3.

The final index pair from our example is (2, 3) which corresponds to

index 8 in the sorted list.

:param int idx: index in sorted list

:return: (lists index, sublist index) pair

"""

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):

"""Build a positional index for indexing the sorted list.

Indexes are represented as binary trees in a dense array notation

similar to a binary heap.

For example, given a lists representation storing integers::

0: [1, 2, 3]

1: [4, 5]

2: [6, 7, 8, 9]

3: [10, 11, 12, 13, 14]

The first transformation maps the sub-lists by their length. The

first row of the index is the length of the sub-lists::

0: [3, 2, 4, 5]

Each row after that is the sum of consecutive pairs of the previous

row::

1: [5, 9]

2: [14]

Finally, the index is built by concatenating these lists together::

_index = [14, 5, 9, 3, 2, 4, 5]

An offset storing the start of the first row is also stored::

_offset = 3

When built, the index can be used for efficient indexing into the list.

See the comment and notes on ``SortedList._pos`` for details.

"""

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):

"""Remove value at `index` from sorted list.

``sl.__delitem__(index)`` <==> ``del sl[index]``

Supports slicing.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList('abcde')

>>> del sl[2]

>>> sl

SortedList(['a', 'b', 'd', 'e'])

>>> del sl[:2]

>>> sl

SortedList(['d', 'e'])

:param index: integer or slice for indexing

:raises IndexError: if index out of range

"""

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])