

'''simple docstring'''



from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

_UpperCamelCase						:  int							       =				TypeVar("KEY")
_UpperCamelCase						:  int							       =				TypeVar("VAL")



@dataclass(frozen=a_     , slots=a_			)
class 				_snake_case					(   Generic[KEY, VAL]			):
  SCREAMING_SNAKE_CASE			:       KEY
  SCREAMING_SNAKE_CASE			:       VAL



class 				_snake_case					(   _Item			):

  def __init__(				self	):





      '''simple docstring'''

      super().__init__(_SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	)


  def __bool__(				self	):





      '''simple docstring'''

      return False



_UpperCamelCase						:  Union[str, Any]							       =				_DeletedItem()



class 				_snake_case					(   MutableMapping[KEY, VAL]			):

  def __init__(				self      , _SCREAMING_SNAKE_CASE = 8      , _SCREAMING_SNAKE_CASE = 0.75	):





      '''simple docstring'''

      lowerCAmelCase 						=							initial_block_size
      lowerCAmelCase 						=							[None] * initial_block_size
      assert 0.0 < capacity_factor < 1.0
      lowerCAmelCase 						=							capacity_factor
      lowerCAmelCase 						=							0

  def   _SCREAMING_SNAKE_CASE				(				self      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      return hash(_SCREAMING_SNAKE_CASE	) % len(self._buckets	)

  def   _SCREAMING_SNAKE_CASE				(				self      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      return (ind + 1) % len(self._buckets	)

  def   _SCREAMING_SNAKE_CASE				(				self      , _SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      lowerCAmelCase 						=							self._buckets[ind]
      if not stored:
          lowerCAmelCase 						=							_Item(_SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	)
          self._len += 1
          return True
      elif stored.key == key:
          lowerCAmelCase 						=							_Item(_SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	)
          return True
      else:
          return False

  def   _SCREAMING_SNAKE_CASE				(				self	):





      '''simple docstring'''

      lowerCAmelCase 						=							len(self._buckets	) * self._capacity_factor
      return len(self	) >= int(_SCREAMING_SNAKE_CASE	)

  def   _SCREAMING_SNAKE_CASE				(				self	):





      '''simple docstring'''

      if len(self._buckets	) <= self._initial_block_size:
          return False
      lowerCAmelCase 						=							len(self._buckets	) * self._capacity_factor / 2
      return len(self	) < limit

  def   _SCREAMING_SNAKE_CASE				(				self      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      lowerCAmelCase 						=							self._buckets
      lowerCAmelCase 						=							[None] * new_size
      lowerCAmelCase 						=							0
      for item in old_buckets:
          if item:
              self._add_item(item.key      , item.val	)

  def   _SCREAMING_SNAKE_CASE				(				self	):





      '''simple docstring'''

      self._resize(len(self._buckets	) * 2	)

  def   _SCREAMING_SNAKE_CASE				(				self	):





      '''simple docstring'''

      self._resize(len(self._buckets	) // 2	)

  def   _SCREAMING_SNAKE_CASE				(				self      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      lowerCAmelCase 						=							self._get_bucket_index(_SCREAMING_SNAKE_CASE	)
      for _ in range(len(self._buckets	)	):
          yield ind
          lowerCAmelCase 						=							self._get_next_ind(_SCREAMING_SNAKE_CASE	)

  def   _SCREAMING_SNAKE_CASE				(				self      , _SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      for ind in self._iterate_buckets(_SCREAMING_SNAKE_CASE	):
          if self._try_set(_SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	):
              break

  def __setitem__(				self      , _SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      if self._is_full():
          self._size_up()

      self._add_item(_SCREAMING_SNAKE_CASE      , _SCREAMING_SNAKE_CASE	)

  def __delitem__(				self      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      for ind in self._iterate_buckets(_SCREAMING_SNAKE_CASE	):
          lowerCAmelCase 						=							self._buckets[ind]
          if item is None:
              raise KeyError(_SCREAMING_SNAKE_CASE	)
          if item is _deleted:
              continue
          if item.key == key:
              lowerCAmelCase 						=							_deleted
              self._len -= 1
              break
      if self._is_sparse():
          self._size_down()

  def __getitem__(				self      , _SCREAMING_SNAKE_CASE	):





      '''simple docstring'''

      for ind in self._iterate_buckets(_SCREAMING_SNAKE_CASE	):
          lowerCAmelCase 						=							self._buckets[ind]
          if item is None:
              break
          if item is _deleted:
              continue
          if item.key == key:
              return item.val
      raise KeyError(_SCREAMING_SNAKE_CASE	)

  def __len__(				self	):





      '''simple docstring'''

      return self._len

  def __iter__(				self	):





      '''simple docstring'''

      yield from (item.key for item in self._buckets if item)


  def __repr__(				self	):





      '''simple docstring'''

      lowerCAmelCase 						=							' ,'.join(
          F'{item.key}: {item.val}' for item in self._buckets if item	)
      return F'HashMap({val_string})'








'''simple docstring'''



import operator


def       snake_case   (	snake_case      : list					,		snake_case      : bool = False					,		snake_case      : list | None = None			) ->  list:


    """simple docstring"""


    lowerCAmelCase 						=							operator.lt if reverse else operator.gt
    lowerCAmelCase 						=							solution or []

    if not arr:
        return solution

    lowerCAmelCase 						=							[arr.pop(0			)]
    for i, item in enumerate(snake_case			):
        if _operator(snake_case					,		sublist[-1]			):
            sublist.append(snake_case			)
            arr.pop(snake_case			)

    #  merging sublist into solution list
    if not solution:
        solution.extend(snake_case			)
    else:
        while sublist:
            lowerCAmelCase 						=							sublist.pop(0			)
            for i, xx in enumerate(snake_case			):
                if not _operator(snake_case					,		snake_case			):
                    solution.insert(snake_case					,		snake_case			)
                    break
            else:
                solution.append(snake_case			)

    strand_sort(snake_case					,		snake_case					,		snake_case			)
    return solution


if __name__ == "__main__":
     assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
     assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]





