


from collections.abc import Callable






class  __magic_name__							:






       def __init__(      self  ,							snake_case = None)						->  None:




          '''simple docstring'''
          # Stores actual heap items.
          _UpperCAmelCase       :       List[str]							   =[]
          # Stores indexes of each item for supporting updates and deletion.
          _UpperCAmelCase       :       List[str]							   ={}
          # Stores current size of heap.
          _UpperCAmelCase       :       Any							   =0
          # Stores function used to evaluate the score of an item on which basis ordering
          # will be done.
          _UpperCAmelCase       :       str							   =key or (lambda snake_case: x)






       def       lowerCAmelCase		(      self  ,							snake_case)						->  int | None:




          '''simple docstring'''
          return int((i - 1) / 2) if i > 0 else None






       def       lowerCAmelCase		(      self  ,							snake_case)						->  int | None:




          '''simple docstring'''
          _UpperCAmelCase       :       List[str]							   =int(2 * i + 1)
          return left if 0 < left < self.size else None






       def       lowerCAmelCase		(      self  ,							snake_case)						->  int | None:




          '''simple docstring'''
          _UpperCAmelCase       :       Optional[Any]							   =int(2 * i + 2)
          return right if 0 < right < self.size else None






       def       lowerCAmelCase		(      self  ,							snake_case  ,							snake_case)						->  None:




          '''simple docstring'''
          _UpperCAmelCase   ,	_UpperCAmelCase       :       Optional[int]							   =(
              self.pos_map[self.arr[j][0]],
              self.pos_map[self.arr[i][0]],
          )
          # Then swap the items in the list.
          _UpperCAmelCase   ,	_UpperCAmelCase       :       List[str]							   =self.arr[j], self.arr[i]






       def       lowerCAmelCase		(      self  ,							snake_case  ,							snake_case)						->  bool:




          '''simple docstring'''
          return self.arr[i][1] < self.arr[j][1]






       def       lowerCAmelCase		(      self  ,							snake_case)						->  int:




          '''simple docstring'''
          _UpperCAmelCase       :       Optional[Any]							   =self._left(__A)
          _UpperCAmelCase       :       Tuple							   =self._right(__A)
          _UpperCAmelCase       :       List[Any]							   =i

          if left is not None and not self._cmp(__A  ,							__A):
             _UpperCAmelCase       :       List[str]							   =left
          if right is not None and not self._cmp(__A  ,							__A):
             _UpperCAmelCase       :       Dict							   =right

          return valid_parent






       def       lowerCAmelCase		(      self  ,							snake_case)						->  None:




          '''simple docstring'''
          _UpperCAmelCase       :       Any							   =self._parent(__A)
          while parent is not None and not self._cmp(__A  ,							__A):
             self._swap(__A  ,							__A)
             _UpperCAmelCase   ,	_UpperCAmelCase       :       str							   =parent, self._parent(__A)






       def       lowerCAmelCase		(      self  ,							snake_case)						->  None:




          '''simple docstring'''
          _UpperCAmelCase       :       Optional[int]							   =self._get_valid_parent(__A)
          while valid_parent != index:
             self._swap(__A  ,							__A)
             _UpperCAmelCase   ,	_UpperCAmelCase       :       Any							   =valid_parent, self._get_valid_parent(__A)






       def       lowerCAmelCase		(      self  ,							snake_case  ,							snake_case)						->  None:




          '''simple docstring'''
          if item not in self.pos_map:
             return
          _UpperCAmelCase       :       Any							   =self.pos_map[item]
          _UpperCAmelCase       :       Union[str, Any]							   =[item, self.key(__A)]
          # Make sure heap is right in both up and down direction.
          # Ideally only one of them will make any change.
          self._heapify_up(__A)
          self._heapify_down(__A)






       def       lowerCAmelCase		(      self  ,							snake_case)						->  None:




          '''simple docstring'''
          if item not in self.pos_map:
             return
          _UpperCAmelCase       :       str							   =self.pos_map[item]
          del self.pos_map[item]
          _UpperCAmelCase       :       Optional[int]							   =self.arr[self.size - 1]
          _UpperCAmelCase       :       Optional[int]							   =index
          self.size -= 1
          # Make sure heap is right in both up and down direction. Ideally only one
          # of them will make any change- so no performance loss in calling both.
          if self.size > index:
             self._heapify_up(__A)
             self._heapify_down(__A)






       def       lowerCAmelCase		(      self  ,							snake_case  ,							snake_case)						->  None:




          '''simple docstring'''
          _UpperCAmelCase       :       Optional[int]							   =len(self.arr)
          if arr_len == self.size:
             self.arr.append([item, self.key(__A)])
          else:
             _UpperCAmelCase       :       Union[str, Any]							   =[item, self.key(__A)]
          _UpperCAmelCase       :       Union[str, Any]							   =self.size
          self.size += 1
          self._heapify_up(self.size - 1)






       def       lowerCAmelCase		(      self)						->  tuple | None:




          '''simple docstring'''
          return self.arr[0] if self.size else None






       def       lowerCAmelCase		(      self)						->  tuple | None:




          '''simple docstring'''
          _UpperCAmelCase       :       int							   =self.get_top()
          if top_item_tuple:
             self.delete_item(top_item_tuple[0])
          return top_item_tuple






def lowerCamelCase__      (						):







   '''simple docstring'''













if __name__ == "__main__":
 import doctest

 doctest.testmod()





'''simple docstring'''






from __future__ import annotations

import bisect





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int	,   __lowerCamelCase	:							int = 0	,   __lowerCamelCase	:							int = -1							):







   '''simple docstring'''




   if hi < 0:
      _UpperCAmelCase       :       int							   =len(__lowerCamelCase							)

   while lo < hi:
      _UpperCAmelCase       :       Dict							   =lo + (hi - lo) // 2
      if sorted_collection[mid] < item:
         _UpperCAmelCase       :       int							   =mid + 1
      else:
         _UpperCAmelCase       :       Union[str, Any]							   =mid

   return lo





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int	,   __lowerCamelCase	:							int = 0	,   __lowerCamelCase	:							int = -1							):







   '''simple docstring'''




   if hi < 0:
      _UpperCAmelCase       :       str							   =len(__lowerCamelCase							)

   while lo < hi:
      _UpperCAmelCase       :       List[Any]							   =lo + (hi - lo) // 2
      if sorted_collection[mid] <= item:
         _UpperCAmelCase       :       Dict							   =mid + 1
      else:
         _UpperCAmelCase       :       Tuple							   =mid

   return lo





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int	,   __lowerCamelCase	:							int = 0	,   __lowerCamelCase	:							int = -1							):







   '''simple docstring'''




   sorted_collection.insert(bisect_left(__lowerCamelCase	,   __lowerCamelCase	,   __lowerCamelCase	,   __lowerCamelCase							)	,   __lowerCamelCase							)





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int	,   __lowerCamelCase	:							int = 0	,   __lowerCamelCase	:							int = -1							):







   '''simple docstring'''




   sorted_collection.insert(bisect_right(__lowerCamelCase	,   __lowerCamelCase	,   __lowerCamelCase	,   __lowerCamelCase							)	,   __lowerCamelCase							)





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int							):







   '''simple docstring'''




   _UpperCAmelCase       :       Optional[int]							   =0
   _UpperCAmelCase       :       Any							   =len(__lowerCamelCase							) - 1

   while left <= right:
      _UpperCAmelCase       :       int							   =left + (right - left) // 2
      _UpperCAmelCase       :       Union[str, Any]							   =sorted_collection[midpoint]
      if current_item == item:
         return midpoint
      elif item < current_item:
         _UpperCAmelCase       :       Optional[Any]							   =midpoint - 1
      else:
         _UpperCAmelCase       :       int							   =midpoint + 1
   return None





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int							):







   '''simple docstring'''




   _UpperCAmelCase       :       Any							   =bisect.bisect_left(__lowerCamelCase	,   __lowerCamelCase							)
   if index != len(__lowerCamelCase							) and sorted_collection[index] == item:
      return index
   return None





def lowerCamelCase__      (						__lowerCamelCase	:							list[int]	,   __lowerCamelCase	:							int	,   __lowerCamelCase	:							int	,   __lowerCamelCase	:							int							):







   '''simple docstring'''




   if right < left:
      return None

   _UpperCAmelCase       :       str							   =left + (right - left) // 2

   if sorted_collection[midpoint] == item:
      return midpoint
   elif sorted_collection[midpoint] > item:
      return binary_search_by_recursion(__lowerCamelCase	,   __lowerCamelCase	,   __lowerCamelCase	,   midpoint - 1							)
   else:
      return binary_search_by_recursion(__lowerCamelCase	,   __lowerCamelCase	,   midpoint + 1	,   __lowerCamelCase							)


if __name__ == "__main__":
 lowercase							=input('Enter numbers separated by comma:\n').strip()
 lowercase							=sorted(int(item) for item in user_input.split(','))
 lowercase							=int(input('Enter a single number to be found in the list:\n'))
 lowercase							=binary_search(collection, target)
 if result is None:
  print(F"""{target} was not found in {collection}.""")
 else:
  print(F"""{target} was found at position {result} in {collection}.""")

